0 
entry="Where in the world is Carmen San Diego"
goal=["Where in the", "world is", "Carmen San Diego"]

我正在尝试创建一个程序，该程序将在“条目”中搜索属于“目标”列表成员的词块。我想保留这些子集中的词序。

这就是我到目前为止所拥有的。我不确定如何完成此操作，或者我是否以正确的方式接近它。

span=1
words = entry.split(" ")
initial_list= [" ".join(words[i:i+span]) for i in range(0, len(words), span)]
x=len(initial_list)
initial_string= " ".join(initial_list)
def backtrack(A,k):
    if A in goal:
        print
    else:
        while A not in goal:
            k=k-1
            A= " ".join(initial_list[0:k])
            if A in goal:
                print A
                words=A.split(" ")
                firstmatch= [" ".join(words[i:i+span]) for i in range(0, len(words), span)]
                newList = []
                for item in initial_list:
                    if item not in firstmatch:
                        newList.append(item)
                nextchunk=" ".join(newList)             

backtrack(initial_string,x)

到目前为止的输出是这样的：

"Where in the"

期望的输出：

"Where in the"
"world is"
"Carmen San Diego"

我一直在努力寻找合适的算法，我认为它需要回溯或搜索修剪，我不太确定。理想情况下，解决方案适用于任何“条目”和“目标”列表。任何意见都非常感谢。

4

2 回答 2

0

这是一个想法：将您的目标列表放入一个树中。在 trie 中查找当前条目字符串的最长匹配前缀，如果找到则将其添加到输出中。

然后在当前条目字符串中找到下一个空格（单词分隔符），将当前条目字符串设置为空格后索引中的子字符串，然后重复直到它为空。

编辑：这里有一些代码。

import string
import datrie

entry="Where in the world is Carmen San Diego"
goal=["Where in the", "world is", "Carmen San Diego"]

dt = datrie.BaseTrie(string.printable)
for i, s in enumerate(goal):
    dt[s] = i

def find_prefix(current_entry):
    try:
        return dt.longest_prefix(current_entry)
    except KeyError:
        return None

def find_matches(entry):
    current_entry = entry

    while(True):
        match = find_prefix(current_entry)
        if match:
            yield match
        space_index = current_entry.find(' ')
        if space_index > 0:
             current_entry = current_entry[space_index + 1:]
        else:
            return

print(list(find_matches(entry)))
于 2014-10-23T22:29:56.800 回答
0

这是做你想做的吗？

entry="Where in the world is Carmen San Diego"
goal=["Where in the", "world is", "Carmen San Diego"]


for word in goal:
    if word in entry:
        print(word)

它只是搜索每个单词的条目并在找到时打印它。

如果要将它们保存到列表或其他内容中，可以执行以下操作：

entry="Where in the world is Carmen San Diego"
goal=["Where in the", "world is", "Carmen San Diego"]
foundwords = []

for word in goal:
    if word in entry:
        foundwords.append(word)
于 2014-10-23T22:32:28.307 回答