查找字典单词

Question

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

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

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

我可以最有效地将单个英语单词从此类复合字符串中分离出来。

Answer 1

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

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

我会研究尝试。使用它，您可以有效地找到（并加权）您的前缀，这正是您要寻找的。

您必须根据良好的字典源自行构建尝试，并在完整单词上对节点进行加权，以便为自己提供良好的质量机制以供参考。

只是在这里集思广益，但如果您知道您的数据集主要由二元组或三元组组成，您可能可以通过多次 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

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

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

PenIsland
KidsExchange
TherapistFinder

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

我发现任何合理的复合词中的子串数量相对较少（最小长度为 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) 的步幅在字符串上滑动，然后简单地检查一组中的每个函数或哈希表。

Answer 7

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

Answer 8

单词的存在可以通过 trie 来完成，或者更简单地通过 set（即哈希表）来完成。给定一个合适的函数，您可以这样做：

# 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.

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

当然，这可能找不到你想要的分割。您可以修改它以返回所有可能的分割（而不仅仅是第一个找到的分割），然后进行某种加权总和，也许可以更喜欢常见的单词而不是不常见的单词。

Answer 9

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

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

ethylmethylketone

语素在哪里：

ethyl methyl and ketone

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

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

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

我们有时会遇到歧义，但仍在寻找报告它的好方法。

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

作为另一个例子，字符串

weeknight

可以被解析为

wee knight

或

week night

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

Answer 10

我会使用以下算法。

1. 从排序后的单词列表开始
   拆分，以及排序列表
   拒绝的话（字典）。

2. 创建对象的结果列表
   应该存储：剩余单词
   和匹配单词的列表。

3. 用单词填充结果列表
   拆分为剩余单词。

4. 遍历结果数组并
   同时查字典——
   总是增加最少的
   二、以类似的方式
   合并算法。这样你就可以
   比较所有可能的匹配
   一次配对。

5. 任何时候你找到匹配项，即
   拆分单词 以 a 开头的单词
   字典单词，替换
   匹配字典单词和
   结果列表中的剩余部分。
   你必须考虑到
   可能的倍数。

6. 只要剩余部分为空，
   您找到了最终结果。

7. 任何时候您找不到匹配的内容
   换句话说，“左侧”
   每次增加结果时
   指针由于不匹配，删除
   相应的结果项。这
   单词没有匹配项，也不可能是
   拆分。

8. 一旦你到达底部
   列表，您将得到一个列表
   部分结果。重复循环
   直到它为空 - 转到第 4 点。