NLP劄記4-字典分詞

NLP劄記4-字典樹

完全切分、正向最長比對和逆向最長比對這三種算法的缺點就是如何判斷集合中是否含有字元串。

如果使用有序集合，複雜度高；
使用散清單，時間複雜度降低，但是記憶體複雜度上去

使用字典樹這種資料結構，速度快、記憶體還省

字典樹

什麼是字典樹

字元串集合常用字典樹（trie樹、字首樹）存儲，字元串上的樹形結構。特點如下

每條邊對應一個數字
從根節點往下構成一個個字元串
字典樹不是在節點上存儲字元串，将詞語視作根節點到某個節點之間的一條路徑
字元串就是一條路徑，從根節點開始，沿着路徑往下走，就可以查詢到該詞語

字典樹的節點實作

每個節點至少有自己的子節點和對應的邊，以及自己是否對應一個詞。如果是map映射而不是集合set ，還需要自己對應的值。

# 節點Node實作

class Node(object):
  def __init__(self, value):
    self._children = {}
    self._value = value

  def _add_child(self, char, value, overwrite=False):
    child = self._children.get(char)   # 先檢查是否存在字元char對應的child
    if child is None:
      child = Node(value)
      self._children[char] = child
    elif overwrite:  # 覆寫
      child._value = value
    return child

複制

字典樹的增删改查

每個節點都是一個狀态，從父節點到子節點的轉義看做是一次狀态轉移。

# 字典樹的實作

class Trie(Node):
  def __init__(self):
    super().__init__(None)  # 魔術方法重載

  def __contains__(self, key):
    return self[key] is not None

  def __getitem__(self, key):
    state = self
    for char in key:
      state = state._children.get(char)
      if state is None:
        return None
    return state._value

  def __setitem__(self, key, value):
    state = self
    for i, char in  enumerate(key):
      if i < len(key) - 1:
        state = state._add_child(char, None, False)
      else:
        state = state._add_child(char, value, True)

# 測試代碼
if __name__ == "__main__":
  trie = Trie()
  # 增
  trie['自然'] = "nature"
  trie['自然人'] = "human"
  assert "自然" in trie

  # 删
  trie['自然'] = None
  assert '自然' not in trie

  # 改
  trie['自然語言'] = 'human language'
  assert trie['自然語言'] == 'human language'

  # 查
  assert trie['入門'] == 'introduction'

複制

首字散列其餘二分的字典樹

散列函數：将對象轉換成整數（散列值）。散列函數的基本要求：對象相同，散列值必須相同。如果對象不同，則散列值也不同，稱之為完美散列。BinTrie的特點是根節點上實施散列政策，其餘節點采用二分查找。

雙數組字典樹

DAT構成

雙數組字典樹，

Double Array Trie，DAT

，是狀态轉移為常數的資料結構。

元素base
下标check

# 狀态b接受字元c轉移到狀态p
# 執行一次加法和整數比較的過程
p = base[b] + c
check[p] = base[b]

複制

實作DAT

class DoubleArrayTrie(object):  # 定義雙數組
  def __init__(self,dic):
    m = JClass("java.util.TreeMap")()
    for k, v in dic.items():
      m[k] = v
    dat = JClass("com.hankcs.hanlp.collection.trie.DoubleArrayTrie")(m)
    self.base = dat.base
    self.check = dat.check
    self.value = dat.v

def char_hash(c):  # python預設的方法是不适合散列函數的，通過Java的hashCode方法
  return JClass('java.lang.Character')(c).hashCode()

def transition(self, c, b):  # 轉移函數實作
  p = self.base(b) + self.char_hase(c) + 1
  if self.base[b] == self.check[p]:
    return p
  else:
    return -1

def __getitem__(self, key):  # 查詢函數
  b = 0
  for i in range(0, len(key)):
    p = self.transition(key[i], b)
    if p is not -1:
      b = p
    else:
      return None

  p = self.base[b]
  n = self.base[p]
  if p == self.check[p] and n < 0:
    index = -n - 1
    return self.value[index]

  return None

複制

AC自動機

DAT全切分的複雜度是O(n^2)，AC自動機的複雜度是O(n)，常用于多字元串搜尋。字典樹是字首樹，從根節點上下來的路徑對應公共路徑。AC自動機在字首樹的基礎上，添加了字尾樹，節省了大量的查詢時間，它的組成分為3個表：

goto表（success表），本質上就是字典樹
fail表
output表

基于雙數組的AC自動機

基本原理是替換

AC

自動機的

goto

表，看作為一顆雙數組字典樹的每個狀态附上額外的資訊。建構原理是為每個狀态

base[i]

和

check[i]

建構

output[i]

和

fail[i]

，具體分為3步：

建構普通的字典樹，讓終結點記住對應模式串的字典順序
建構雙數組字典樹，在将每個狀态映射到雙數組中時，記住每個狀态在雙數組中的下标位置
建構 AC 自動機， fail 表中存儲的就是狀态的下标

準确率評測

混淆矩陣

四種組合的解釋：

TP：預測是P，真實值也是P———真陽
FP：預測是P，真實值是N———假陽
FN：預測是N，真實值是P———假陰
TN：預測是N，真實值也是N———真陰

精準率precision

精準率指的是，在預測為P的結果中，正類數量占據全部結果的比率。分母是預測為陽性的數目

P=\frac{TP}{TP+FP}

召回率recall

召回率指的是，在正類樣本中，被找出來的比率。在搜尋引擎評測中，召回率為相關網頁被搜尋到的比率。分母是真實值為陽性的數目

R=\frac{TP}{TP+FN}

筆記：P和R是兩個互相對立的名額：一個變大，另一個必然變小

F1值

值指的是精準率和召回率的調和平均值

F_1=\frac{2PR}{P+R}

中文分詞中P\R\F_1的計算

混淆矩陣針對的是答案和預測數量相等的情況。中文分詞中，标準答案和分詞結果的單詞書不一定是相等的。

混淆矩陣針對的是分類問題
中文分詞針對的是分塊問題

長度為n的字元串，分詞結果是一系列的單詞，單詞在文本的起止位置記作區間[i,j],1\leq i \leq j \leq n 。如下假設：

标準答案構成區間為A，作為正類（答案為P），區間之外構成負類

記分詞結果所有單詞區間構成集合B（預測結果為P）

\begin{array}{l}{P=\frac{|A \cap B|}{|B|}} \ {R=\frac{|A \cap B|}{|A|}}\end{array}

def to_region(segmentation):
  region = []
  start = 0
  for word in re.compile("\\s+").split(segmentation.strip()):
    end = start + len(word)
    region.append((start, end))
    start = end
  return region

def prf(gold, pred):
  sizeA, sizeB, capAB = 0, 0, 0
  with open(gold) as gd, open(pred) as pd:
    for g, p in zip(gd, pd):
      A, B = set(to_region(g)), set(to_region(p))
      sizeA += len(A)
      sizeB += len(B)
      capAB += len(A &  B)
  p,r = capAB / sizeB, capAB / sizeA
  return p, r, 2*p*r/(p*r)

複制

字典樹的其他應用

停用詞過濾

停用詞指的是沒有什麼意義的詞語，比如“的”、“甚至”等，去掉了對整個句子沒有什麼影響

簡繁轉化

簡體中文和繁體中文之間的互相轉化。HanLP将中文分為簡體s、繁體t、台灣正體tw、香港繁體hk4這4種。

拼音轉換

将拼音轉換為漢字的問題。