将字符串与要迭代检索的列表匹配

Question

有两个列表，一个由句子的字符序列组成，另一个由单词组成。你知道吗

目标是将第一个列表的项与第二个列表的项匹配length of li_a (len(li_a))次。相同的匹配词将临时保存为候选词。在最终的迭代过程之后，将选择最长的单词作为我们的预期结果，并将其添加到新的列表中。你知道吗

因为li_a中有18个字符，所以假设literation time是18。你知道吗

li_a = ['T','h','o','m','a','s','h','a','d','a','h','a','r','d','t','i','m','e']
li_words = ['a','The','Thomas','have','had','has','hard','hot','time','tea']

首先，li_a中的第一项与li_words匹配。你知道吗

1. 'T' => li_words || li_a[0] => li_words
2. 'Th' => li_words || li_a[0]+li_a[1] => li_words
3. 'Tho' => li_words || li_a[0]+li_a[1]+li_a[2] => li_words
...
6. 'Thomas' => li_words || li_a[0]+..+li_a[5] => li_words (marks as candidate when the match is found)
...
18. 'Thomashadahardtime' => li_words || li_a[0]..li_a[17] => li_words

上面的例子显示了第一个迭代过程应该如何完成。它给我们一个候选者的结果是Thomas。但是，从第一个到第二个的li_a项将被扣除

li_a = ['h','a','d','a','h','a','r','d','t','i','m','e']

第二个迭代过程和前一个一样应该被执行来检索下一个单词。你知道吗

最后，列表的最终结果应该是这样的：

final_li = ['Thomas','had','a','hard','time']

尝试

下面的尝试适用于查找最长的匹配，但不适用于迭代工作，并且在li_words中缺少单词时不会给出准确的结果

def matched_substring(li1, li2):
    new_li = []
    tmp = ''
    for a in li1:
        tmp += a
        count = 0
        for b in li2:
            if tmp == b:
                count += 1
        if count == 0:
            tmp1 = tmp.replace(a, '')
            new_li.append(tmp1)
            tmp = a
    if li2.__contains__(tmp):
        new_li.append(tmp) 
    return new_li

它返回为：['Thomas', 'h', 'a', 'd', 'a', 'h', 'a', 'r', 'd', 't', 'i', 'm']

UNICODE中的字符

string_a = "['ဒီ|စစ်|ဆေး|မှု|ကို|သီး|ခြား|လွတ်|လပ်|တဲ့|ပု|ဂ္ဂို|လ်|တ|ဦး|က|ဦး|ဆောင်|ခိုင်း|တာ|ဟာ|လူ|ထု|အ|ကျိုး|အ|တွက်|ဖြစ်|တယ်|လို့|တ|ရား|ရေး|ဝန်|ကြီး|ဌာ|န|က|ထုတ်|ပြန်|တဲ့|ကြေ|ညာ|ချက်|ထဲ|မှာ|ဖေါ်|ပြ|ထား|ပါ|တယ်']"

要将以上字符串转换为列表：

##Get rid of brackets & punctuation marks
strp_str = string_a.strip("[]")
strp_str = strp_str.strip("'")
##Now we achieve *li_a* 
li_a = strp_str.split('|')

链接到li_words列表的剪贴板：mm-words.txt

##Get all the words in List
read_words = open('mm-words.txt','r')
##Achieve them in List    
li_words = read_words.read().split('\n')

##Now run into function
print analyze(li_a, li_words)

Answer 1

这里有一个使用itertools的函数方法：

import itertools
li_a = ['T','h','o','m','a','s','h','a','d','a','h','a','r','d','t','i','m','e']
li_words = ['a','The','Thomas','have','had','has','hard','hot','time','tea']
res = list(itertools.imap(lambda x: max(itertools.ifilter(lambda y: x in y, li_words), key=len), li_a))
res
['Thomas', 'Thomas', 'Thomas', 'Thomas', 'Thomas', 'Thomas', 'Thomas', 'Thomas', 'hard', 'Thomas', 'Thomas', 'Thomas', 'hard', 'hard', 'time', 'time', 'Thomas', 'have']

其思想是，对于li_a中的每个字母，我们过滤出该字母所在的单词，然后在该集合上使用max，使用len取最大的一个。你知道吗

以下是每个字母对应的拉链：

zip(li_a, res)
[('T', 'Thomas'), ('h', 'Thomas'), ('o', 'Thomas'), ('m', 'Thomas'), ('a', 'Thomas'), ('s', 'Thomas'), ('h', 'Thomas'), ('a', 'Thomas'), ('d', 'hard'), ('a', 'Thomas'), ('h', 'Thomas'), ('a', 'Thomas'), ('r', 'hard'), ('d', 'hard'), ('t', 'time'), ('i', 'time'), ('m', 'Thomas'), ('e', 'have')]

Answer 2

也许您可以尝试匹配由li_a生成的字符串，例如

>>> li_a = ['T','h','o','m','a','s','h','a','d','a','h','a','r','d','t','i','m','e']
>>> li_words = ['a','The','Thomas','have','had','has','hard','hot','time','tea']
>>>
>>> s = "".join(li_a)
>>> for i in sorted(li_words,key=lambda x:-len(x)):
...     if i in s:
...         s=s.replace(i,str(li_words.index(i))+",")
...
>>> [li_words[int(i)] for i in s[:-1].split(",")]
['Thomas', 'had', 'a', 'hard', 'time']

希望这有帮助。你知道吗

Answer 3

为了获得所有可能的解决方案（如果还有一些“重叠”的单词），可以首先为每个单词找到该特定单词可能出现的所有起始位置。然后策略是从字符串的开头开始，测试可以出现在这里的所有候选字符，并将字符串中相应数量的字符向前移动。在这个新的位置，这个过程被重复（由于递归，所有的组合都被探索）。一旦我们到达字符串的末尾，就找到了一个成功的解决方案。你知道吗

li_a = ['T', 'h','o','m','a','s','h','a','d','a','h','a','r','d','t','i','m','e','a']
li_words = ['a','The','Thomas','have','had','has','hard','hot','time','tea','timea']


def analyze(li_a, li_words):

    s = ''.join(li_a)

    #for each word, find all its positions in s
    stat = {}
    for word in li_words:
        pos = s.find(word)
        while pos != -1:
            if not pos in stat:
                stat[pos] = []
            stat[pos].append(word)
            pos = s.find(word, pos + 1)

    solutions = []

    def check(idx, solution):
        if idx == len(s):
            solutions.append(solution)
            return

        #at position idx, test all candidates and call
        #itself recursively
        words = stat.get(idx, [])
        for word in words:
            check(idx + len(word), solution + [word])

    #start at the beginning
    check(0, [])

    return solutions

print(analyze(li_a, li_words))

编辑：

我测试了您的Unicode输入，似乎string_a包含一个单词ဖေါ်，而mm-words.txt中缺少这个单词。另一方面，在这种情况下，提议的解决方案无论如何都会失败。首先，在pos = s.find(word, pos + len(word))中有一个错误，它应该是pos = s.find(word, pos + 1)，以便找到特定单词的所有重叠出现。更重要的是，令人厌恶的复杂性要求（本质上是指数级的扩展）使得它在如此大的输入上无法使用。方法是采用dynamic programming approach。在下面的示例中，我只从string_a（保存到str.txt）中选取前10个单词，以避免丢失一个：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def read_data(fname, delim, uniq = False):
    with open(fname, 'r') as F:
        data = F.read().split(delim)
        data = map(lambda s: s.decode('utf-8').strip(), data)
        data = filter(lambda s: s, data)
        if uniq:
            data = list(set(data))
    return data

li_a = read_data('str.txt', '|')
li_words = read_data('mm-words.txt', '\n', uniq = True)

def analyze(li_a, li_words):
    words = set(li_words)

    s = ''.join(li_a[0:10])
    N = len(s)

    solutions = [ [] for idx in range(0, N) ]
    S = [False for idx in range(0, N)]

    for i in range(0, N):
        flag = False
        if (s[0:i+1] in words):
            flag = True
            solutions[i].append([s[0:i+1], -1])

        else:
            for j in range(1, i+1):
                if S[j-1] and (s[j:i+1] in words):
                    #save the newly identified word and reference to solution
                    #previously found at location j-1
                    solutions[i].append([s[j:i+1], j-1])

                    #break #find only one solution
                    flag = True
        S[i] = flag

    splittings = []
    def assemble(pos, L):
        if pos == -1:
            splittings.append(L)
            return
        for w,idx in solutions[pos]:
            assemble(idx, [w] + L)

    assemble(N-1, [])
    return splittings

splittings = analyze(li_a, li_words)
for splitting in splittings:
    print(' | '.join(splitting).encode('utf-8'))

这将产生：

ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့