algorithm - 查找字典单词

Question

我有很多由两三个英文单词组合而成的复合字符串。

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

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

我可以将单个英语单词与此类复合字符串分开最有效的方法是什么。

score 8 · Accepted Answer

我不确定您需要多少时间或频率来执行此操作（它是一次性操作吗？每天？每周？）但您显然需要快速、加权的字典查找。

您还需要一个冲突解决机制，也许是一个边队列来手动解决具有多种可能含义的元组上的冲突。

我会调查Tries。使用一个你可以有效地找到（和加权）你的前缀，这正是你要寻找的。

您必须自己从一个好的字典源构建 Tries，并根据完整的单词对节点进行加权，以便为自己提供一个高质量的参考机制。

只是在这里进行头脑风暴，但是如果您知道您的数据集主要由 duplets 或triplets 组成，您可能会通过多次Trie 查找而侥幸，例如查找“Spic”，然后查找“ejet”，然后发现两个结果的得分都较低，放弃“Spice”和“Jet”，这两种尝试都会在两者之间产生良好的组合结果。

此外，我会考虑对最常见的前缀进行频率分析，直至达到任意或动态限制，例如过滤“the”或“un”或“in”并相应地对它们进行加权。

听起来像一个有趣的问题，祝你好运！

score 4 · Accepted Answer

如果您回答的目标是找到“输入的最大可能分解”，那么如果您使用一些图论，算法可能会相当简单。您使用复合词并在每个字母之前和之后制作一个带有顶点的图形。对于字符串中的每个索引，您将拥有一个顶点，并且在结尾处有一个顶点。接下来，您会在字典中找到所有作为复合词子串的合法词。然后，对于每个合法的子字符串，将权重为 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。

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

score 2 · Accepted Answer

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

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

score 2 · Accepted Answer

你将如何决定如何划分事物？环顾网络，您会发现一些 URL 示例，这些示例最终具有其他含义。

假设你没有资本继续下去，你会用这些做什么（目前想到的，我知道还有更多。）：

PenIsland
KidsExchange
TherapistFinder

最后一个特别有问题，因为麻烦的部分是两个单词一起运行但不是复合词，当你打破它时，意思就完全改变了。

score 2 · Accepted Answer

那么，给定一个单词，它是由另外两个英语单词组成的复合词吗？您可以为所有此类复合词提供某种查找表，但如果您只是检查候选人并尝试与英语单词进行匹配，您将得到误报。

编辑：看起来我必须去提供一些例子。我想到的词包括：

accustomednesses != accustomed + nesses
adulthoods != adult + hoods
agreeabilities != agree + abilities
willingest != will + ingest
windlasses != wind + lasses
withstanding != with + standing
yourselves != yours + elves
zoomorphic != zoom + orphic
ambassadorships != ambassador + ships
allotropes != allot + ropes

这是一些尝试说明这一点的python代码。在磁盘上为自己准备一本字典，然后尝试一下：

from __future__ import with_statement

def opendict(dictionary=r"g:\words\words(3).txt"):
    with open(dictionary, "r") as f:
        return set(line.strip() for line in f)

if __name__ == '__main__':
    s = opendict()
    for word in sorted(s):
        if len(word) >= 10:
            for i in range(4, len(word)-4):
                left, right = word[:i], word[i:]
                if (left in s) and (right in s):
                    if right not in ('nesses', ):
                        print word, left, right

score 1 · Accepted Answer

最近有人问了一个类似的问题：分词算法。如果您想限制拆分的数量，您将跟踪每个元组中的拆分数量（所以不是一对，而是一个三元组）。

score 1 · Accepted Answer

这可能是一个非常困难的问题，并且没有简单的通用解决方案（可能存在适用于小子集的启发式方法）。

我们在化学中正面临这个问题，其中名称是由语素的串联组成的。一个例子是：

ethylmethylketone

其中词素是：

ethyl methyl and ketone

我们通过自动机和最大熵来解决这个问题，代码在 Sourceforge 上可用

http://www.sf.net/projects/oscar3-chem

但请注意，这将需要一些工作。

我们有时会遇到模棱两可的情况，但仍在寻找报告的好方法。

要区分 penIsland 和 penisLand 需要特定领域的启发式方法。可能的解释将取决于所使用的语料库——没有任何语言问题独立于所分析的领域或领域。

作为另一个例子，字符串

weeknight

可以解析为

wee knight

或者

week night

两者都是“正确的”，因为它们遵循“adj-noun”或“noun-noun”的形式。两者都“有意义”，选择哪一个将取决于使用领域。在奇幻游戏中，前者的可能性更大，而在商业游戏中后者的可能性更大。如果您遇到此类问题，那么拥有经过专家注释的约定使用语料库将很有用（技术上是自然语言处理中的“黄金标准”）。

score 1 · Accepted Answer

我突然想到，任何合理的复合词都有相对较少的子串（最小长度为 2）。例如对于“spicejet”，我得到：

'sp', 'pi', 'ic', 'ce', 'ej', 'je', 'et',
'spi', 'pic', 'ice', 'cej', 'eje', 'jet',
'spic', 'pice', 'icej', 'ceje', 'ejet',
'spice', 'picej', 'iceje', 'cejet',
'spicej', 'piceje', 'icejet',
'spiceje' 'picejet'

... 26 个子字符串。

因此，找到一个函数来生成所有这些（使用 2、3、4 的步幅滑过你的字符串……(len(yourstring) - 1)然后简单地检查一组或哈希表中的每一个。

score 1 · Accepted Answer

单词的存在可以用 trie 来完成，或者更简单地用一个集合（即哈希表）来完成。给定一个合适的功能，你可以这样做：

# python-ish pseudocode
def splitword(word):
    # word is a character array indexed from 0..n-1

    for i from 1 to n-1:
        head = word[:i]  # first i characters
        tail = word[i:]  # everything else

        if is_word(head):
            if i == n-1:
                return [head]   # this was the only valid word; return it as a 1-element list
            else:
                rest = splitword(tail)
                if rest != []:   # check whether we successfully split the tail into words
                    return [head] + rest

    return []  # No successful split found, and 'word' is not a word.

基本上，只是尝试不同的断点，看看我们是否可以造词。递归意味着它将回溯，直到找到成功的拆分。

当然，这可能找不到您想要的拆分。您可以对其进行修改以返回所有可能的拆分（而不仅仅是找到的第一个拆分），然后进行某种加权求和，也许是为了更喜欢常用词而不是不常用词。

score 0 · Accepted Answer

我会使用以下算法。

从要拆分的单词的排序列表和拒绝单词的排序列表（字典）开始。
创建应存储的对象的结果列表：剩余单词和匹配单词列表。
用要拆分为剩余单词的单词填充结果列表。
同时遍历结果数组和字典——总是以类似于合并算法的方式增加两者中的最小值。通过这种方式，您可以一次比较所有可能的匹配对。
每当您找到匹配项，即以字典单词开头的拆分单词单词时，替换匹配的字典单词和结果列表中的剩余部分。您必须考虑可能的倍数。
任何时候剩余部分为空时，您都会找到最终结果。
每当您在“左侧”找不到匹配项时，换句话说，每次由于不匹配而增加结果指针时，都删除相应的结果项。此单词没有匹配项，也无法拆分。
到达列表底部后，您将获得部分结果列表。重复循环，直到它为空——转到第 4 点。

algorithm - 查找字典单词

10 回答 10

Related

Reference