Python：基于字典的分词

Question

我有一个字典：

dict = ["as", "ass", "share", "rest"]

给定一个字符串input :

string = "xassharest"

我希望展示基于此类字典的所有可能构成的单词：

[('x', 'as', 's', 'h', 'a', 'rest'), ('x', 'as', 'share', 's', 't'), ('x', 'ass', 'h', 'a', 'rest')]

实际上，我已经尝试了使用字符串的所有组合（使用itertools库），但这需要很长时间。以下是我的代码：

def getallpossiblewords(string):
    allwords = preprocessingcorpus("corpus.txt")
    temp = []
    for i in range(0, len(string)):
        for j in range(1, len(string) + 1):
            if string[i:j] in allwords:
                temp += [string[i:j]]

    allposwords = sorted(temp, key=len, reverse=True)
    #print(allposwords)
    return allposwords

def wordseg(string):
    a = string
    b = getallpossiblewords(string)
    cuts = []
    allpos = []
    for i in range(0,len(a)):
        cuts.extend(combinations(range(1,len(a)),i))
    for i in cuts:
        last = 0
        output = []
        for j in i:
            output.append(a[last:j])
            last = j
        output.append(a[last:])
        for x in range(len(output)):
            if output[x] in b:
                allpos += [output]
                #print(output)
    #print(allpos)

    fixallpos = list()
    for sublist in allpos:
        if sublist not in fixallpos:
            fixallpos.append(sublist)

我需要最快的算法来解决这个问题，因为输入字符串可能会更长。

有人能解决我的问题吗？

- user8642658

---

这看起来像是一道作业题。你应该说明这是否属实。你还应该展示你已经尝试过什么，并提到你遇到的具体问题。参见：https://stackoverflow.com/help/how-to-ask - user1531971

你所称之为字典的对象：dict=["a","as","ass","share","rest"] 在Python中并不是字典。你需要对你想要提问的话题进行一些研究，试着自己回答问题，然后再来这里寻求帮助。 - Dr t

jdv：谢谢您的建议，我已经编辑了我的帖子。顺便问一下，您能帮我吗？Dr t：那个词典只是举例，是的，我正在进行研究，我已经使用CRF（基于机器学习的算法）解决了这个问题，但我需要其他算法（基于词典的）。也许你能帮我？ - user8642658

为什么你提供的解决方案不包括 ["a", "ssh", "a", "rest"]？为什么它包括 ["a","s","sha","rest"] 呢？我没有看到分割 "ssha" 或不分离第二个 "a" 的理由。我们中有一个人还没有理解这个问题。 - Prune

谢谢，普鲁恩。不好意思，我是新来的，请指导一下。顺便说一句，我已经更改了我的确切问题。你能听明白吗？ - user8642658

Answer 1

这似乎是一个完美的递归使用 str.partition() 的例子。 下面是我的示例实现，我不会声称它解决了每个问题（因为几乎没有测试用例），而是试图推销这种特定方法：

def segmented(string):

    segmentations = set()

    for word in words:
        before, match, after = string.partition(word)

        if not match:
            continue

        prefixes = segmented(before) or [before]
        suffixes = segmented(after) or [after]

        if prefixes and suffixes:
            for prefix in prefixes:
                for suffix in suffixes:
                    segmentations.add((*prefix, word, *suffix))
        elif prefixes:
            for prefix in prefixes:
                    segmentations.add((*prefix, word, *suffixes))
        elif suffixes:
            for suffix in suffixes:
                    segmentations.add((*prefixes, word, suffix))
        else:
            segmentations.add((*prefixes, word, *suffixes))

    return segmentations

words = ["as", "ass", "share", "rest"]

print(segmented("xassharest"))

输出

% python3 test.py
{('x', 'as', 's', 'h', 'a', 'rest'), ('x', 'as', 'share', 's', 't'), ('x', 'ass', 'h', 'a', 'rest')}
%

- cdlane