Python中部分指定單詞的最佳匹配

Question

我有一個文件dict.txt，其中包含英語中的所有單詞。

用戶將輸入他們的字：

x = raw_input("Enter partial word: ")

實施例的輸入將是：RN，--n，-U-，他 - O，H-LLO等，未知字符會最好用下劃線而不是（ - ）來指定。

我想讓程序想出一個列表，找出字典中找到的所有最佳匹配。

示例：如果部分單詞是r--，列表將包含run，ran，rat，rob等。

有沒有辦法使用for循環做到這一點？

Answer 1

一個簡單的方法可以使用regular expressions。由於目前還不清楚這個問題是否是功課，所以細節留給讀者閱讀。

Answer 2

我發生了幾種方法;第一個是將你的字典預處理爲單詞[wordlength] [offset] [charAtOffset] = set（匹配單詞）;那麼你的查詢成爲所有相關單詞集的交集。速度非常快，但內存密集且需要大量設置工作。

例：

# search for 'r-n' 
matches = list(words[3][0]['r'] & words[3][2]['n']) 

第二個是使用正則表達式的詞典的線性掃描;速度慢得多，但內存佔用最小。

例：

import re 

foundMatch = re.compile('r.n').match 
matches = [word for word in allWords if foundMatch(word)] 

三將是一個遞歸搜索到文字特里;

四 - 這聽起來像你想要的東西 - 是一個天真的字匹配：

with open('dictionary.txt') as inf: 
    all_words = [word.strip().lower() for word in inf] # one word per line 

find_word = 'r-tt-r' 
matching_words = [] 
for word in all_words: 
    if len(word)==len(find_word): 
     if all(find==ch or find=='-' for find,ch in zip(find_word, word)): 
      matching_words.append(word) 

編輯：對於第一種選擇完整的代碼如下：

from collections import defaultdict 
import operator 

try: 
    inp = raw_input # Python 2.x 
except NameError: 
    inp = input  # Python 3.x 

class Words(object): 
    @classmethod 
    def fromFile(cls, fname): 
     with open(fname) as inf: 
      return cls(inf) 

    def __init__(self, words=None): 
     super(Words,self).__init__() 
     self.words = set() 
     self.index = defaultdict(lambda: defaultdict(lambda: defaultdict(set))) 
     _addword = self.addWord 
     for word in words: 
      _addword(word.strip().lower()) 

    def addWord(self, word): 
     self.words.add(word) 
     _ind = self.index[len(word)] 
     for ind,ch in enumerate(word): 
      _ind[ind][ch].add(word) 

    def findAll(self, pattern): 
     pattern = pattern.strip().lower() 
     _ind = self.index[len(pattern)] 
     return reduce(operator.__and__, (_ind[ind][ch] for ind,ch in enumerate(pattern) if ch!='-'), self.words) 

def main(): 
    print('Loading dict... ') 
    words = Words.fromFile('dict.txt') 
    print('done.') 

    while True: 
     seek = inp('Enter partial word ("-" is wildcard, nothing to exit): ').strip() 
     if seek: 
      print("Matching words: "+' '.join(words.findAll(seek))+'\n') 
     else: 
      break 

if __name__=="__main__": 
    main() 

Answer 3

而不是使用_表示通配符，用\ w代替。將\ b添加到模式的開始和結尾，然後通過正則表達式匹配器運行字典。 So -un ---變成：

>>> import re 
>>> re.findall(r'\b\wun\w\w\w\b', "run runner bunt bunter bunted bummer") 
['runner', 'bunter', 'bunted'] 

\ w匹配任何'單詞字符'。 \ b匹配任何字邊界。

Answer 4

聽起來像作業涉及搜索算法什麼的，但我會給你一個開始。

一種解決方案可能是將文件索引（如果這可以在合理的時間內完成）到樹結構中，每個字符代表一個節點值，每個子代都是後續字符。然後，您可以使用輸入作爲地圖遍歷樹。一個字符表示要去的下一個節點，而破折號表示它應該包含所有的子節點。每當你擊中一片葉子時，n等級會以n爲輸入長度來加深，你知道你找到了一個匹配。

好的是，一旦你索引，你的搜索將大大加快。這是一個可以永遠走索引...

Answer 5

需要一點記憶，但這樣做的伎倆：

import re 
import sys 

word = '\\b' + sys.argv[1].replace('-', '\\w') + '\\b' 
print word 

with open('data.txt', 'r') as fh: 
    print re.findall(word, fh.read()) 

Answer 6

如果你想這樣做，反覆您應該創建一個索引：

wordlist = [word.strip() for word in "run, ran, rat, rob, fish, tree".split(',')] 

from collections import defaultdict 

class Index(object): 

    def __init__(self, wordlist=()): 
     self.trie = defaultdict(set) 
     for word in wordlist: 
      self.add_word(word) 

    def add_word(self, word): 
     """ adds word to the index """ 
     # save the length of the word 
     self.trie[len(word)].add(word)  
     for marker in enumerate(word): 
      # add word to the set of words with (pos,char) 
      self.trie[marker].add(word) 


    def find(self, pattern, wildcard='-'): 
     # get all word with matching length as candidates 
     candidates = self.trie[len(pattern)] 

     # get all words with all the markers 
     for marker in enumerate(pattern):    
      if marker[1] != wildcard: 
       candidates &= self.trie[marker] 

      # exit early if there are no candicates 
      if not candidates:     
       return None 

     return candidates 


with open('dict.txt', 'rt') as lines: 
    wordlist = [word.strip() for word in lines] 

s = Index(wordlist) 
print s.find("r--") 

Tries用於搜索字符串。這是一個簡單的前綴trie，使用單個字典。