如何根據現有的模式分佈將序列劃分爲不同長度的元組？

我對patterns舉行的各種言語模式有一個先驗概率分佈。我還擁有一系列從詞標記化獲得的詞性標記列表，編號爲sequences。如何根據現有的模式分佈將序列劃分爲不同長度的元組？

我想將sequences中的每個列表劃分爲任意數量的不相交的片段，其中每個片段存在於patterns中，並且聯合概率被最大化。

例如，序列['NN', 'VBG', 'CC', 'VBG']將理想地劃分爲以下：[('NN',), ('VBG',), ('VBG',)]。

我想不出一種效率非常低的方法。也許如果patterns被組織在某種樹形結構中會有幫助嗎？

patterns = {('NN',): 0.40132345717065276, 
      ('VBG',): 0.22273379631859294, 
      ('JJ', 'NN'): 0.075111492116086656, 
      ('NN', 'NN'): 0.056656296053708859, 
      ... 
      ('NN', 'NN', 'VBG'): 0.00039491807857906547, 
      ('RB', 'VBD'): 0.00033712518903090955, 
      ('NN', 'CD'): 0.00019264296516051976, 
      ('VBG', 'NN'): 0.0017337866864446778} 

sequences = [['NN', 'VBG', 'CC', 'VBG'], 
      ['JJ', 'NNS', 'VBP', 'RB', 'JJ', 'JJ', 'NN'], 
      ['JJ', 'NN'], 
      ['JJ', 'NNP', 'JJ', 'NNS']]

來源

2014-01-22 Pedro Silva

您可以將其視爲一個分詞問題，並通過動態編程有效地解決它。將您的PoS標籤序列看作是由空格分隔的而不是（如中文情況）。任務是插入「空格」，以便「有意義」。

我將使用以下術語：

每詞類標記是一個character
的PoS標籤，例如每序列NN或(JJ NN)，是word，由characters組成。
每個詞w的評分爲s(w)。這是由您的patterns字典實施的。 s(w') = 0所有生詞w'
分割的得分組合在分割

我們需要一些東西去一個算法的所有字的分數（如總和）：

存儲所述第一i字符的分割的最佳可能得分
一種arrary L[i]指定的數組B[i]其中最後間隙（字之間的空間）前字符i是
B[0] = 0和B[1] = s(c_0)，其中c_0是第一個字符
P[0] = 0
B[i] = max(B[j] + s(c_j...c_i))所有0 < j < i，其中c_j...c_i是通過從i位置的所有字符形成爲定位j包容的單詞。

的算法如下：

B[0] = 0 
B[1] = s(sequence[0:1]) 
for i in 0...len(sequence): 
    B[i] = 0 
    for j in 0...i: 
     candidate = s(sequence[i:j]) + B[j] 
     if candidate > B[i]: 
      B[i] = candidate 
      P[i] = j 
for beg, end in consecutive_pairs(P): # 
    print c_beg...c_end

此僞代碼填充B具有最佳分數，並P與「空間」的位置。

注意事項：

該解決方案是最佳的相對於給定的分數功能s。看看你的問題，s(NN) + s(NN) >> s(NN NN)。這意味着將NN NN序列分割爲兩個詞(NN, NN)而不是單個詞(NN NN,)會更好。你可能需要調整你的分數功能。
將未知單詞的分數設置爲0是有意的。這確保NN CC NN被分割爲三個詞(NN, CC, NN)而不是(NN CC, NN)或(NN, CC NN)或(NN CC NN,)。這可能是也可能不是你想要的，請編輯你的問題，如果它不是
這可能是我的索引是一個關，我太累了，現在告訴。上面的代碼應該足以讓你開始。這是一個標準的算法，可以隨意引用你喜歡的任何一本教科書。

來源

2014-01-22 11:49:36 mbatchkarov

太棒了！我沒有想到它在分詞方面。相反，我一直在用集合分割和類似方法來考慮它。讓我在實施這個方面有一個很好的解決方案，我會回過頭來接受解決方案。有一件事：'L'（最後一個間隙數組）在你的僞代碼中稍後會變成'P'。 –

如何根據現有的模式分佈將序列劃分爲不同長度的元組？

回答

相關問題