3

我收到一个字，有些信不见了。我需要将所有可能的匹配词返回到这个模式。例如我收到__erf_ow我需要返回overflow

如果我得到模式_a_，我需要返回：cat bag......所有长度为 3 且第二个字母是

给定所有单词的字典 - 存储它的最佳方式是什么，或者使用哪种算法来快速找到所有相关单词？

编辑：最好的意思是运行时间。我不在乎存储数据需要多少时间（只要完成），但我想快速给出答案。显而易见的答案是哈希表，但这张表会很大。

4

4 回答 4

1

“最佳”取决于您拥有的资源。

这是我要做的：

  1. 为每个单词长度存储一个单独的字典。
  2. 我假设您的搜索不区分大小写！为每个字存储一个 32 位值，如果字符a..z出现在字中，则在其中设置 0 到 25 位。将单词存储在 a 中Map<Integer, List<String>>（key 是 32 位值，value 是该键的所有单词的列表）

如何搜索：

  1. 用想要的长度的单词拿字典
  2. 为您的模式创建 32 位值。

  3. 迭代所有键Map并检查键是否按位和模式的 32 位值等于模式的 32 位值。如果不是，这不能匹配。如果此检查通过，仅匹配是不够的，因为它不处理字符顺序或出现多个字符。但是查的很快，不需要看单词的每个字符。

  4. 通过将列表中每个单词的字符与您的模式进行比较，迭代列表中的列表Map并检查它们是否与您的模式真正匹配。

示例：三个字母单词的字典：the、cat、bag、nor、ega、atc、ron；

-> Hashvalues
     00000000000010000000000010010000   the
     00000000000010000000000000000101   cat, atc
     00000000000000000000000001000011   bag
     00000000000000100110000000000000   nor, ron
     00000000000000000000000001010001   age, ega

 Value for pattern _a_ is 00000000000000000000000000000001

Step 3 returns that the keys 
      00000000000010000000000000000101,  
      00000000000000000000000001000011 and 
      00000000000000000000000001010001 are candidates for matches.



Step 4 returns: 'cat' and 'bag'
于 2013-05-26T19:42:22.067 回答
0

Levenshtein 距离可以帮助你。还有其他字符串相似度函数。考虑到您的限制，您可以使用自己的距离函数。此外，换能器是个好主意。这是研究这个想法的良好开端，同样，您将不得不努力使其适合您自己的问题。

如果正如 Dukeling 下面所说，您需要减少运行时间，那么您可以使用一些紧凑的数据结构（如小波树）来执行此操作，并对节点进行访问/范围/排名查询（最好的情况是 log2 的大小字母表），但同样，你必须让它适合你自己的问题。

于 2013-05-26T19:59:25.707 回答
0

如果您不介意内存效率非常低，您可以将单词集存储在哈希表中 - 其中关键是模式（我相信这应该是获取数据的最快算法之一）：

trees = {}


def init(filename):
    with open(filename) as f:
        for word in f:
            word = word.strip()
            s = trees.get((len(word),0,''), set())
            s.add(word)
            trees[(len(word),0,'')] = s
            for i,c in enumerate(word):
                s = trees.get((len(word),i,c), set())
                s.add(word)
                trees[(len(word),i,c)] = s


def words_for_pattern(pattern):
    pattern = pattern.lower()
    words = trees[(len(pattern),0,'')]
    for i, c in enumerate(pattern):
        if c in "abcddefghijklmnopqrstuvwxyz":
            words = words.intersection(trees[(len(pattern),i,c)])

    return words

if __name__ == '__main__':
    init('english-words.20')
    while (True):
        pattern = raw_input("Enter pattern: ")
        print words_for_pattern(pattern)


 Enter pattern: **ll*
>>> set(['balls', 'rolls', 'hills', 'cells', 'polls', 'jelly', 'bills', 'pills', 'jolly', 'halls', 'bells'])

这trees是一个映射，其中键是 3 元组：(word-length, character index, character)每个键的值是所有单词的集合，其中长度为和word-lengthwith character。character index此外，还有包含特定长度的所有单词的特殊键。

在获取模式的单词时，我将模式中每个非空白字符的单词集相交。

于 2013-05-26T20:38:23.773 回答
0

如果您使用按字母排序的 HashMap，它看起来会更小吗？

 ArrayList<HashMap<Character, ArrayList<String>>> dictionary;

HashMap 的第一个字符是指示符，哪个字母是单词的一部分。

第一个 ArrayList 可以存储每个单词，List 的索引可以显示，什么 Character 存储在哪里。所以你可以用 -a- 获取单词：dictionary.get(2).get(a)。结果：每个单词都有一个，第二名。

第二个 ArrayList 存储单词。

于 2013-05-26T19:30:12.323 回答