快捷導(dǎo)航

Python Trie樹實(shí)現(xiàn)字典排序

更新時(shí)間：2014年03月28日 23:47:20 投稿：mdxy-dxy

Trie樹是一種很常用的樹結(jié)構(gòu)，它被廣泛用于各個(gè)方面，比如字符串檢索、中文分詞、求字符串最長(zhǎng)公共前綴和字典排序等等，而且在輸入法中也能看到Trie樹的身影

一般語言都提供了按字典排序的API，比如跟微信公眾平臺(tái)對(duì)接時(shí)就需要用到字典排序。按字典排序有很多種算法，最容易想到的就是字符串搜索的方式，但這種方式實(shí)現(xiàn)起來很麻煩，性能也不太好。Trie樹是一種很常用的樹結(jié)構(gòu)，它被廣泛用于各個(gè)方面，比如字符串檢索、中文分詞、求字符串最長(zhǎng)公共前綴和字典排序等等，而且在輸入法中也能看到Trie樹的身影。

什么是Trie樹

Trie樹通常又稱為字典樹、單詞查找樹或前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)。如圖數(shù)字的字典是一個(gè)10叉樹：

同理小寫英文字母或大寫英文字母的字典數(shù)是一個(gè)26叉樹。如上圖可知，Trie樹的根結(jié)點(diǎn)是不保存數(shù)據(jù)的，所有的數(shù)據(jù)都保存在它的孩子節(jié)點(diǎn)中。有字符串go, golang, php, python, perl，它這棵Trie樹可如下圖所示構(gòu)造：

我們來分析下上面這張圖。除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)只存儲(chǔ)一個(gè)字符。go和golang共享go前綴，php、perl和python只共用p前綴。為了實(shí)現(xiàn)字典排序，每一層節(jié)點(diǎn)上存儲(chǔ)的字符都是按照字典排序的方式存儲(chǔ)(這跟遍歷的方式有關(guān))。我們先來看看對(duì)單個(gè)字符如何進(jìn)行字典排序。本文只考慮小寫字母，其它方式類似。'a'在'b'的前面，而'a'的ASCII碼小于'b'的ASCII碼，因此通過它們的ASCII相減就可以得到字典順序。而且python內(nèi)置了字典排序的API，比如：

復(fù)制代碼代碼如下:

#!/usr/bin/env python
#coding: utf8

if __name__ == '__main__':
arr = [c for c in 'python']
arr.sort()
print arr

而且也可以使用我之前的一篇文章介紹的bitmap來實(shí)現(xiàn)：Python: 實(shí)現(xiàn)bitmap數(shù)據(jù)結(jié)構(gòu) 。實(shí)現(xiàn)代碼如下：

復(fù)制代碼代碼如下:

#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
def __init__(self, max):
self.size  = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]

def calcElemIndex(self, num, up=False):
  '''up為True則為向上取整, 否則為向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

def calcBitIndex(self, num):
return num % 31

def set(self, num):
  elemIndex = self.calcElemIndex(num)
  byteIndex = self.calcBitIndex(num)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem | (1 << byteIndex)

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1 << byteIndex))

def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1 << byteIndex):
   return True
  return False

if __name__ == '__main__':
MAX = ord('z')
suffle_array = [c for c in 'python']
result       = []
bitmap = Bitmap(MAX)
for c in suffle_array:
  bitmap.set(ord(c))

for i in range(MAX + 1):
  if bitmap.test(i):
   result.append(chr(i))

print '原始數(shù)組為:    %s' % suffle_array
print '排序后的數(shù)組為: %s' % result

bitmap的排序不能有重復(fù)字符。其實(shí)剛才所說的基于ASCII碼相減的方式進(jìn)行字典排序，已經(jīng)有很多成熟算法了，比如排序、希爾排序、冒泡排序和堆排序等等。本文為了圖簡(jiǎn)單，將使用Python自帶的sorted方法來進(jìn)行單字符的字典排序。如果讀者自行實(shí)現(xiàn)單字符數(shù)組的排序也可以，而且這樣將可以自定義字符串的排序方式。

實(shí)現(xiàn)思路

整個(gè)實(shí)現(xiàn)包括2個(gè)類：Trie類和Node類。Node類表示Trie樹中的節(jié)點(diǎn)，由Trie類組織成一棵Trie樹。我們先來看Node類：

復(fù)制代碼代碼如下:

#!/usr/bin/env python
#coding: utf8

class Node(object):
def __init__(self, c=None, word=None):
  self.c          = c    # 節(jié)點(diǎn)存儲(chǔ)的單個(gè)字符
  self.word       = word # 節(jié)點(diǎn)存儲(chǔ)的詞
  self.childs     = []   # 此節(jié)點(diǎn)的子節(jié)點(diǎn)

Node包含三個(gè)成員變量。c為每個(gè)節(jié)點(diǎn)上存儲(chǔ)的字符。word表示一個(gè)完整的詞，在本文中指的是一個(gè)字符串。childs包含這個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)。既然在每個(gè)節(jié)點(diǎn)中存儲(chǔ)了c，那么存儲(chǔ)word有什么用呢？并且這個(gè)word應(yīng)該存在哪個(gè)節(jié)點(diǎn)上呢？還是用剛才的圖舉例子：比如go和golang，它們共用go前綴，如果是字符串搜索倒好辦，因?yàn)闀?huì)提供原始字符串，只要在這棵Trie樹上按照路徑搜索即可。但是對(duì)于排序來說，不會(huì)提供任何輸入，所以無法知道單詞的邊界在哪里，而Node類中的word就是起到單詞邊界作用。具體是存儲(chǔ)在單詞的最后一個(gè)節(jié)點(diǎn)上，如圖所示：

而Node類中的c成員如果這棵樹不用于搜索，則可以不定義它，因?yàn)樵谂判蛑兴皇潜仨毜摹?/p>

接下來我們看看Trie類的定義：

復(fù)制代碼代碼如下:

#!/usr/bin/env python
#coding: utf8

'''Trie樹實(shí)現(xiàn)字符串?dāng)?shù)組字典排序'''

class Trie(object):
def __init__(self):
self.root  = Node() # Trie樹root節(jié)點(diǎn)引用

def add(self, word):
  '''添加字符串'''
  node = self.root
  for c in word:
   pos = self.find(node, c)
   if pos < 0:
    node.childs.append(Node(c))
    #為了圖簡(jiǎn)單，這里直接使用Python內(nèi)置的sorted來排序
    #pos有問題，因?yàn)閟ort之后的pos會(huì)變掉,所以需要再次find來獲取真實(shí)的pos
    #自定義單字符數(shù)組的排序方式可以實(shí)現(xiàn)任意規(guī)則的字符串?dāng)?shù)組的排序
    node.childs = sorted(node.childs, key=lambda child: child.c)
    pos = self.find(node, c)
   node = node.childs[pos]
  node.word = word

def preOrder(self, node):
  '''先序輸出'''
  results = []
  if node.word:
   results.append(node.word)
  for child in node.childs:
   results.extend(self.preOrder(child))
  return results

def find(self, node, c):
  '''查找字符的位置'''
  childs = node.childs
  _len   = len(childs)
  if _len == 0:
   return -1
  for i in range(_len):
   if childs[i].c == c:
    return i
  return -1

def setWords(self, words):
for word in words:
self.add(word)

Trie包含1個(gè)成員變量和4個(gè)方法。root用于引用根結(jié)點(diǎn)，它不存儲(chǔ)具體的數(shù)據(jù)，但是它擁有子節(jié)點(diǎn)。setWords方法用于初始化，調(diào)用add方法來初始化Trie樹，這種調(diào)用是基于每個(gè)字符串的。add方法將每個(gè)字符添加到子節(jié)點(diǎn)，如果存在則共用它并尋找下一個(gè)子節(jié)點(diǎn)，依此類推。find是用于查找是否已經(jīng)建立了存儲(chǔ)某個(gè)字符的子節(jié)點(diǎn)，而preOrder是先序獲取存儲(chǔ)的word。樹的遍歷方式有三種：先序遍歷、中序遍歷和后序遍歷，如果各位不太明白，可自行Google去了解。接下我們測(cè)試一下：

復(fù)制代碼代碼如下:

#!/usr/bin/env python
#coding: utf8

'''Trie樹實(shí)現(xiàn)字符串?dāng)?shù)組字典排序'''

class Trie(object):
def __init__(self):
self.root  = Node() # Trie樹root節(jié)點(diǎn)引用

def add(self, word):
  '''添加字符串'''
  node = self.root
  for c in word:
   pos = self.find(node, c)
   if pos < 0:
    node.childs.append(Node(c))
    #為了圖簡(jiǎn)單，這里直接使用Python內(nèi)置的sorted來排序
    #pos有問題，因?yàn)閟ort之后的pos會(huì)變掉,所以需要再次find來獲取真實(shí)的pos
    #自定義單字符數(shù)組的排序方式可以實(shí)現(xiàn)任意規(guī)則的字符串?dāng)?shù)組的排序
    node.childs = sorted(node.childs, key=lambda child: child.c)
    pos = self.find(node, c)
   node = node.childs[pos]
  node.word = word

def preOrder(self, node):
  '''先序輸出'''
  results = []
  if node.word:
   results.append(node.word)
  for child in node.childs:
   results.extend(self.preOrder(child))
  return results

def find(self, node, c):
  '''查找字符的位置'''
  childs = node.childs
  _len   = len(childs)
  if _len == 0:
   return -1
  for i in range(_len):
   if childs[i].c == c:
    return i
  return -1

def setWords(self, words):
for word in words:
self.add(word)

class Node(object):
def __init__(self, c=None, word=None):
  self.c          = c    # 節(jié)點(diǎn)存儲(chǔ)的單個(gè)字符
  self.word       = word # 節(jié)點(diǎn)存儲(chǔ)的詞
  self.childs     = []   # 此節(jié)點(diǎn)的子節(jié)點(diǎn)

if __name__ == '__main__':
words = ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
trie = Trie()
trie.setWords(words)
result = trie.preOrder(trie.root)
print '原始字符串?dāng)?shù)組:     %s' % words
print 'Trie樹排序后:       %s' % result
words.sort()
print 'Python的sort排序后: %s' % words

結(jié)束語

樹的種類非常之多。在樹結(jié)構(gòu)的實(shí)現(xiàn)中，樹的遍歷是個(gè)難點(diǎn)，需要多加練習(xí)。上述代碼寫得比較倉促，沒有進(jìn)行任何優(yōu)化，但在此基礎(chǔ)上可以實(shí)現(xiàn)任何方式的字符串排序，以及字符串搜索等。