python: word segmentation based on dictionary

Admin 1
Viewed 1778

I am having a dictionary :

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

and a string input :

string = "xassharest"

And i want to show all possible words can made based on dictionary like this :

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

Actually i've tried it using all combinations of string (using library itertools) but it takes so long. Here is my code :

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)

I need the fastest algorithm to solve this problem, because the input of string may be even longer.

Can anyone solve my problem?

nlp python
1 Answers

This seems like a perfect recursive use of str.partition(). Below is my example implementation that I won't claim solves every problem (since there are practically no test cases) but rather tries to do a selling job on this particular approach:

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"))

OUTPUT

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