使用字典分隔後綴

Question

我需要從給定單詞中分離所有可能的後綴（大約1000）。我正在考慮使用字典。

在這樣做時，我會將後綴作爲關鍵字（以及關於後綴的其他信息作爲進一步過程中所需的值）。如果最長可能的後綴是4個字母，我會搜索詞典中所有可能的組合。 例如： 給定一個詞：'abcdefg'我會搜索'g'，'fg'，'efg'和'defg'的詞典。

我已經做了一些研究，並沒有發現字典的很多類似的用法。這可能是一個可行的解決方案，或者我在這裏錯過了什麼？幫助很多appriciated。

Answer 1

如果後綴不是太長，你的解決方案細的聲音 - 這是隻有少數字典每個字看起坐，和字典查找窗口快。我不認爲更復雜的解決方案（比如使用trie）在這裏值得。爲了僅刪除後綴，您也可以使用集合而不是字典，但由於您需要每個後綴的附加信息，字典似乎是自然選擇。

Answer 2

最簡單（可能不是最快）的方法是查找列表中的所有匹配項。有1000件產品，你不應該有太多的性能問題。

>>> sufx = ['foo', 'bar'] 
>>> [s for s in sufx if 'bazbar'.endswith(s)] 
['bar'] 
>>>[s for s in sufx if 'bazbaz'.endswith(s)] 
[] 
>>> [s for s in sufx if 'bazfoo'.endswith(s)] 
['foo'] 

Answer 3

我不確定我是否正確理解您的用例。我想這是關於你正在處理後綴的事實，他們很難被發現。

一個典型的方法（通常在索引情況下）將是圍繞你的字符串，並將後綴作爲前綴處理。然後，您可以在反轉後綴的排序列表中進行簡單的二分搜索（因此前綴）。

Answer 4

如果我明白你想要做什麼，你應該使用標準庫中的re模塊。

文檔是在這裏：

http://docs.python.org/library/re.html#module-re

這裏有關於副詞的例子：

http://docs.python.org/library/re.html#finding-all-adverbs

至於他們作爲存儲在字典鍵，似乎沒什麼問題。特別是，如果你想對其他處理有後綴的字詞進行處理，

Answer 5

參見Time Complexity of a dict。字典查找時間非常快（平均O（1）！）。對於這個實現，找到最長後綴的平均時間複雜度將是O（k^2），其中k是你單詞的長度。由於''.join操作（由於字符串不支持O（1）appendleft操作，將需要類似的O（n）操作（如反轉或字符串切片），因此該值爲k^2。

做的簡單方法（測試蟒蛇3）：

>>> from collections import deque 
>>> word = "antidisestablishmentarianism" 
>>> suffixes = {'ism': 3, 'anism': 6, 'ment': 4, 'arianism': 12} 
>>> suffix = deque() 
>>> longest = None 
>>> for char in reversed(word): 
...  suffix.appendleft(char) 
...  suf = ''.join(suffix) 
...  if suf in suffixes: 
...   longest = suf 
... 
>>> longest 
'arianism'