寻找字典单词

Question

我有很多复合字符串,它们是两个或三个英文单词的组合.

    e.g. "Spicejet" is a combination of the words "spice" and "jet"

我需要将这些单独的英语单词与这些复合字符串分开.我的字典将包含大约100000个单词.

什么是最有效的,我可以将单个英语单词与这些复合字符串分开.

Answer 1

我不确定你需要花多少时间或频率(这是一次性操作？每天？每周？)但你显然想要一个快速,加权的字典查找.

您还希望有一个冲突解决机制,也许是一个副队列来手动解决具有多种可能含义的元组的冲突.

我会看看特里斯.使用一个你可以有效地找到(并加权)你的前缀,这正是你要寻找的.

你必须自己从一个好的字典源中构建Tries,并在完整的单词上加权节点,为自己提供一个高质量的参考机制.

只是在这里集思广益,但如果你知道你的数据集主要由duplets或triplets组成,那么你可能可以通过多个Trie查找,例如查找'Spic'然后'ejet',然后发现两个结果都得分很低,放弃'Spice'和'Jet',两者之间的两个尝试都会产生良好的综合效果.

此外,我会考虑对最常见的前缀使用频率分析,直到任意或动态限制,例如过滤'the'或'un'或'in'并相应地加权.

听起来很有趣,祝你好运!

Answer 2

如果您的目标是找到“输入的最大可能分解”，那么如果您使用一些图论，那么该算法可能会相当简单。您使用复合词并制作一个图表，每个字母之前和之后都有一个顶点。字符串中的每个索引都会有一个顶点，并且在末尾有一个顶点。接下来，您将在词典中查找属于复合词子串的所有合法单词。然后，对于每个合法子字符串，向图中添加一条权重为 1 的边，将子字符串中第一个字母之前的顶点与子字符串中最后一个字母之后的顶点连接起来。最后，使用最短路径算法找到第一个顶点和最后一个顶点之间边数最少的路径。

伪代码是这样的：

parseWords(compoundWord)
    # Make the graph
    graph = makeGraph()
    N = compoundWord.length
    for index = 0 to N
        graph.addVertex(i)

    # Add the edges for each word
    for index = 0 to N - 1
        for length = 1 to min(N - index, MAX_WORD_LENGTH)
            potentialWord = compoundWord.substr(index, length)
            if dictionary.isElement(potentialWord)
                graph.addEdge(index, index + length, 1)

    # Now find a list of edges which define the shortest path
    edges = graph.shortestPath(0, N)

    # Change these edges back into words.
    result = makeList()
    for e in edges
        result.add(compoundWord.substr(e.start, e.stop - e.start + 1))
    return result

显然，我还没有测试过这个伪代码，并且可能存在一些逐一索引错误，并且没有任何错误检查，但基本思想是存在的。我在学校做过类似的事情，效果很好。边创建循环为 O(M * N)，其中 N 是复合词的长度，M 是字典中的最大单词长度或 N（以较小者为准）。最短路径算法的运行时间将取决于您选择的算法。最容易想到的是Dijkstra 。我认为它的运行时间是 O(N^2 * log(N))，因为可能的最大边是 N^2。

您可以使用任何最短路径算法。有几种最短路径算法，它们有各自的优点和缺点，但我猜对于您的情况，差异不会太大。如果您不想找到尽可能少的单词来分解复合词，而是想找到最多可能的单词，那么您可以给边赋予负权重，并尝试使用允许负权重的算法找到最短路径。

Answer 3

在我看来，您想将字典存储在Trie或 DAWG 数据结构中。

Trie 已经将单词存储为复合词。因此，“spicejet”将存储为“spice jet ”，其中 * 表示单词的结尾。您所要做的就是在字典中查找复合词并记录您击中了多少个词尾终止符。从那里你必须尝试每个子字符串（在这个例子中，我们还不知道“jet”是否是一个单词，所以我们必须查找它）。