在单词列表中查找复合词 - Python

Question

我有一个需要过滤的简单单词列表，但列表中的每个单词都附加了一个附带的“分数”，这给我带来了一些麻烦。输入列表具有以下结构：lst = ['FAST;5','BREAK;60','FASTBREAK;40',        'OUTBREAK;110','BREAKFASTBUFFET;35',               'BUFFET;75','FASTBREAKPOINTS;60'       ]我试图弄清楚如何识别列表中仅由同一列表中的其他单词组成的单词。例如，应用于lst上面的代码将产生：ans = ['FASTBREAK:40','BREAKFASTBUFFET;35']我发现一个先前的问题涉及几乎相同的情况，但在这种情况下，列表中的单词没有跟踪分数，并且我在处理列表中的这些跟踪分数时遇到了麻烦。该ans列表必须保留找到的复合词的分数。中的单词顺序lst是随机且无关的。理想情况下，我希望 ans 列表按单词的长度（在 之前' ; '）排序，如上所示。这将为我节省一些额外的 ans 后处理。我已经找到了一种使用 ReGex 和嵌套 for 循环的方法（我会让你免去我 1980 年代风格的暴力代码的丑陋，它真的不漂亮），但我的单词列表有接近一百万个条目，我的解决方案需要很长时间才能完全无法使用。我正在寻找一个我可以实际使用的更具 Python 风格的解决方案。我很难解决这个问题。

Answer 1

有多种方法可以加快该过程，但我怀疑是否存在多项式解决方案。

因此，让我们使用多重处理，并尽我们所能来生成有意义的结果。下面的示例与您所要求的并不相同，但它确实从一本大词典中组成了一个明显复合词的列表。

对于下面的代码，我正在获取https://gist.github.com/h3xx/1976236，其中按英语频率顺序列出了大约 80,000 个唯一单词。

如果预先按字母顺序对输入单词列表进行排序，则可以轻松加快下面的代码，因为复合词的每个头将立即跟随其潜在的复合成员：

black

blackberries

blackberry

blackbird

blackbirds

blackboard

blackguard

blackguards

blackmail

blackness

blacksmith

blacksmiths

正如评论中提到的，您可能还需要使用语义过滤器来识别真正的复合词 - 例如，“一般”一词不是“基因集会”的复合词！因此，虽然您可能会获得竞争者列表，但您需要以某种方式消除误报。

# python 3.9

import multiprocessing as mp

# returns an ordered list of lowercase words to be used.

def load(name) -> list:

    return [line[:-1].lower() for line in open(name) if not line.startswith('#') and len(line) > 3]

# function that identifies the compounds of a word from a list.

# ... can be optimised if using a sorted list.

def compounds_of(word: str, values: list):

    return [w for w in values if w.startswith(word) and w.removeprefix(word) in values]

# apply compound finding across an mp environment

# but this is the slowest part

def compose(values: list) -> dict:

    with mp.Pool() as pool:

        result = {(word, i): pool.apply(compounds_of, (word, values)) for i, word in enumerate(values)}

    return result

if __name__ == '__main__':

    # https://gist.github.com/h3xx/1976236

    words = load('wiki-100k.txt')  # words are ordered by popularity, and are 3 or more letters, in lowercase.

    words = list(dict.fromkeys(words))

    # remove those word heads which have less than 3 tails

    compounds = {k: v for k, v in compose(words).items() if len(v) > 3}

    # get the top 500 keys

    rank = list(sorted(compounds.keys(), key=lambda x: x[1]))[:500]

    # compose them into a dict and print

    tops = {k[0]: compounds[k] for k in rank}

    print(tops)

Answer 2

我想我会这样做：创建一个仅包含单词的新列表。在 for 循环中遍历此列表，并在其中查找属于外循环单词的一部分的单词。如果找到：用空字符串替换找到的部分。如果随后整个单词被空字符串替换：显示原始列表中相应索引的单词。

编辑：正如评论中所指出的，在某些情况下代码可能存在问题，例如：lst = ["BREAKFASTBUFFET;35", "BREAK;60", "BREAKFAST;18", "BUFFET;75"] 在 BREAKFASTBUFFET 中，我首先发现 BREAK 是其中的一部分，所以我用空字符串替换了该代码，这阻止找到早餐。我希望可以通过按单词长度降序对列表进行排序来解决这个问题。

编辑2
我之前的编辑并不是完美无缺的，比如有一个词BREAKFASTEN，它不应该被BREAKFAST“吃掉”。该版本执行以下操作：

• 列出候选者列表：调查中单词的所有单词

• 制作另一个以该单词开头的单词列表

• 跟踪候选列表中您已经尝试过的单词

• 一会儿正确：继续尝试，直到开始列表为空，或者您已成功地将所有单词替换为候选单词

lst = ['FAST;5','BREAK;60','FASTBREAK;40',

       'OUTBREAK;110','BREAKFASTBUFFET;35',

       'POINTS;25',

       'BUFFET;75','FASTBREAKPOINTS;60', 'BREAKPOINTS;15'

      ]

lst2 = [ s.split(';')[0] for s in lst ]

for i, word in enumerate(lst2):

    # candidates: words that are part of current word

    candidates = [ x for i2, x in enumerate(lst2) if x in word and i != i2 ]

    if len(candidates) > 0:

        tried = []

        word2 = word

        found = False

        while not found:

            # start: subset of candidates that the current word starts with

            start = [ x for x in candidates if word2.startswith(x) and x not in tried ]

            for trial in start:

                word2 = word2.replace(trial,'')

                tried.append(trial)

                if len(word2)==0:

                    print(lst[i])

                    found = True

                    break

            if len(candidates)>1:

                candidates = candidates[1:]

                word2=candidates[0]

            else:

                break

Answer 3

这是一些完成这项工作的代码。我确信它并不适合您的情况（有一百万个条目），但也许在某些方面有用：

#!/usr/bin/env python                                                           

                                                                                  

from collections import namedtuple                                                 

                                                                                 

Word = namedtuple("Word", ("characters", "number"))                                

separator = ";"    

                                                                             

lst = [                                                                            

    "FAST;5",                                                                      

    "BREAK;60",                                                                    

    "FASTBREAK;40",                                                                

    "OUTBREAK;110",                                                                

    "BREAKFASTBUFFET;35",                                                          

    "BUFFET;75",                                                                   

    "FASTBREAKPOINTS;60",                                                          

]                                                                                  

                                                                                 

words = [Word(*w.rsplit(separator, 1)) for w in lst]                                     

                                                                                 

                                                                                 

def findparts(oword, parts):                                                       

    if len(oword.characters) == 0:                                                 

        return parts                                                               

    for iword in words:                                                            

        if not parts and iword.characters == oword.characters:                     

            continue                                                               

        if iword.characters in oword.characters:

            parts.append(iword)                                                    

            characters = oword.characters.replace(iword.characters, "")                                                

            return findparts(Word(characters, oword.number), parts)                

    return []                                                                      

                                                                                 

                                                                                 

ans = []                                                                           

for word in words:                                                                 

    parts = findparts(word, [])                                                    

    if parts:                                                                      

        ans.append(separator.join(word))    

                                                                                 

print(ans)

它使用递归函数，获取列表中的单词并尝试将其与同一列表中的其他单词组合起来。此功能还将向您展示形成复合词的实际原子词。

然而，它并不是很聪明。以下是它不会检测的组合示例：[BREAKFASTBUFFET, BREAK, BREAKFAST, BUFFET]。

它使用了一个命名元组来暂时将实际单词与附加到它的数字分开，假设分隔符始终是;。

我不认为正则表达式比简单的字符串搜索有优势。

如果您知道有关复合词组成的更多条件，例如组件的最大数量，itertools组合生成器可能会帮助您显着加快速度并避免错过上面给出的示例。