Trie？在python中匹配帶尾字符的單詞

Question

這與stackoverflow上的絕大多數問題有點不同（是的，我花時間搜索和閱讀），所以請耐心等待。

我有文字A，如：allow *，apolog *等。總共有成千上萬的這樣的條目。而且我有文件B包含一個文本的主體，與成千上萬的單詞。我希望能夠在FILE A.

例匹配的話在我的文字的話在文件B：

文件B的 「道歉」 將匹配文件中的 「apolog *」

文件B的「一個」既不匹配‘允許*’，也不是‘apolog *’

文件B的‘apologizetomenoworelseiwillkillyou’也將匹配文件的‘apolog *’

任何人都可以建議的算法/數據結構（即最好是DO-能夠在Python中），這可以幫助我實現這是什麼？我研究過的這些嘗試似乎更多地將匹配前綴到整個單詞，但在這裏，我將整個單詞匹配到前綴。因爲它們有固定的規則，所以干擾算法不存在問題，而在這種情況下，我的後綴可以是任何東西。我不想遍歷FILE A中的整個列表，因爲這需要太多時間。

如果這很混亂，我很樂意澄清。謝謝。

Answer 1

將所有前綴放在散列表中。然後取B中的每個單詞並在散列表中查找它的所有前綴。你得到的任何命中都表示比賽。

所以散列表將包含「允許」和「道歉」。對於「道歉」，您會查找「a」，然後「ap」，依此類推，直到您查找「apolog」並找到匹配。

Answer 2

如果我理解您要查找的內容，您希望能夠看到文件A中與文件B中的給定完整詞匹配的所有前綴。特里數據結構允許您將單個前綴與列表進行匹配的全文，但你需要去另一個方向。

如果是這樣，您仍然可以使用一個trie進行匹配，使用查找表來反轉結果。算法如下：

• 迭代文件B中的單詞，將它們放入一個句號中。
• 迭代文件A中的前綴，查找trie中的匹配項。
  • 對於每個匹配，將前綴添加到由匹配的詞索引的列表字典中。

這裏是一些代碼實現算法。你需要一個名爲Trie特里類（在同一時間使用發電機，如果你不希望值都在內存中）傳入的參數words和prefixes iterables：

def matchPrefixes(words, prefixes): 
    """Returns a word-to-prefix lookup table.""" 

    trie = Trie() 
    for word in words: 
     trie.add(word) 

    lookupTable = defaultdict(list) 
    for prefix in prefixes: 
     matchedWords = trie.matchPrefix(prefix) 

     for word in matchedWords: 
      lookupTable[word].append(prefix) 

    return lookupTable 

這應該是兩個相當有效時間和記憶，尤其是當單詞列表比前綴列表短得多時。與任何單詞不匹配的前綴在針對特里樹檢查後都不會使用任何內存。

Answer 3

如果文件B中的單詞數量遠遠大於文件A中的前綴，則還可以構建一個前綴列表並匹配其中的單詞。

如果你瞭解Trie的工作方式，這將會容易得多。 Trie是一個用字符串構建的樹，如下所示。在Trie中匹配一個字符串是從根部走到其中一個葉子的過程。

在你的問題中，如果我們把前綴放在Trie中，並查找單詞，我們將需要標記Trie中的一些內部節點作爲前綴的終止。當我們在Trie中查找一個單詞時，每當我們到達一個標記爲前綴終止的節點時，我們都會將該前綴添加爲與該單詞「匹配」。 （然後我們繼續閱讀下一封信）。

這完全是@ Blckknght解決方案的逆向解決方案。哪個更有效率取決於哪個文件A和文件B更大。

In @ Blckknght的解決方案中，Trie中的每個節點都由一組單詞（其路徑）包含該節點進行標記。前綴的搜索結束於前綴的最後一個字母。當它停止時，我們將搜索停止的Trie節點，然後我們添加節點上標記爲與前綴匹配的集合。

如果對任何人都有幫助，我會寫一些pududo代碼。

Trie from wiki, from which you can find some code in "Algorithms" part

Answer 4

假設您有在每個文件10萬個字。

排序= N *的log（n） 二進制搜索查找=的log（n）

所以這是最壞的情況下的n * log（n）的

其是100，000 *日誌（100， 000）= 100,000 * 11 = 10^6 =幾乎是即時的

我不認爲你需要什麼幻想與這樣的小文件。簡單的排序和二進制搜索：

__author__ = 'Robert' 

from bisect import bisect_right 

file_a = """hell* 
wor* 
howard* 
are* 
yo* 
all* 
to*""".splitlines() 

file_b = """hello world how are you all today too told town""".split() 

a_starts = sorted(word[:-1] for word in file_a) #can do this easily if only 100, 000 words as you say. 

def match(word): 
    pos = bisect_right(a_starts, word) 
    #assert 0 <= pos < len(a_starts) 
    matched_word = a_starts[pos - 1] 
    return matched_word if word.startswith(matched_word) else None 

for word in file_b: 
    print(word, " -> ", match(word)) 

""" 
hello -> hell 
world -> wor 
how -> None 
are -> are 
you -> yo 
all -> all 
today -> to 
too -> to 
told -> to 
town -> to 
"""