匹配部分填充词的算法(Algorithm for matching partially filled words)

匹配部分填充词的算法(Algorithm for matching partially filled words)

我正在写一个游戏，当给出一个部分填充的单词时，搜索字典并返回所有匹配的单词。 为此，我试图找到一种可用于上述目的的算法。 例如，给定 - - a - ，算法将在字典中搜索长度为4且“a”为第三个字母的所有单词。

是否有这样的算法？ 如果没有，有人可以大致了解如何设计这样的算法吗？

提前致谢。

I am writing a game which when given a partially filled word, searches a dictionary and returns all the matching words. To that effect, I am trying to find an algorithm that can be used for the said purpose. For example, given - - a -, the algorithm will search a dictionary for all the words which have length 4 and have 'a' as the third letter.

Is there such an algorithm already? If not, can somebody given a rough idea of how to design such an algorithm?

Thanks in Advance.

最满意答案

嗯，它还没有存在，但是已经在SO上研究过填字游戏问题。

我提出的解决方案的要点是按字母和索引索引，这是Python给出的：

class Index: def __init__(self, list): self.data = defaultdict(set) for word in list: self.add(word) def add(self, word): for l in range(0, len(word)): self.data[(l, word[l])].insert(word) def look(self, letters): """letters is a list of tuples (position, letter)""" result = None for (p,l) in letters: set = self.data[(p,l)] if result == None: result = set else: result = result.insersection(set) return result

这个想法很简单：你有一个大的索引，每个夫妇都有一组单词(position,letter) 。 在你的情况下，它可以扩展为每个单词长度有一个索引，这将减少单词集的大小，从而更快。

对于检索，您只需将所有集合相交以具有与所有已知字母匹配的公共单词集。

Well, it does not already exists, but it's been researched on SO already, for crosswords problems.

The gist of the solution I proposed was to index by letter and indexes, which is Python gives:

class Index: def __init__(self, list): self.data = defaultdict(set) for word in list: self.add(word) def add(self, word): for l in range(0, len(word)): self.data[(l, word[l])].insert(word) def look(self, letters): """letters is a list of tuples (position, letter)""" result = None for (p,l) in letters: set = self.data[(p,l)] if result == None: result = set else: result = result.insersection(set) return result

The idea is simple: you have a large index which has a set of words for each couple (position,letter). It could be extended, in your case, to have one index per word length, which would dimish the size of the sets of words and thus be faster.

For retrieval, you simply intersect all the sets to have the common set of word that matches all the known letters.