역 추적/검색 정리 - 조합 단어 검색 파이썬에서

Question

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" 

나는 이것에 대한 적절한 알고리즘을 찾기 위해 노력하고 내 바퀴를 돌고 있었고, I 백 트랙킹 또는 검색 프 루닝이 필요하다고 생각합니다. 정말 잘 모르겠습니다. 이상적으로, 솔루션은 모든 "입력"및 "목표"목록에서 작동합니다. 모든 의견을 많이 보내 주시면 감사하겠습니다.

Answer 1

다음은 아이디어입니다. 목표 목록을 트라이에 넣으십시오. 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))) 

Answer 2

이 작업이 원하는 작업을 수행합니까?

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)