Parsowanie ciągów przy użyciu języka Python?

Question

Podając ciąg znaków, taki jak "helloyellowellow", przeanalizuj wszystkie poprawne łańcuchy z danego ciągu. (Np .: [[hell, hello, yellow], [low, low] ........]

Poszukuję najbardziej zoptymalizowanego sposobu napisania kodu. Oto mój, ale nie jestem pewien, czy jest to najlepszy sposób

Pełne ujawnienie - to było pytanie wywiad

master = [] 

# Dictionary for us to look up words 
def is_word(inputstr): 
    #returns True/False 


def processstring(fstr,secstr,li): 
    if is_word(fstr): 
     li.append(fstr) 
    if len(secstr) == 0: 
     if len(li) != 0: 
      master.append(li) 
     return 
    processstring(fstr+secstr[0], secstr[1:len(secstr)],li) 



def wrapperprocess(inpstr): 
    li = [] 
    if len(inpstr) == 0: 
     return 
    processstring('',inpstr,li) 
    wrapperprocess(inpstr[1:len(inpstr)]) 


wrapperprocess('helloyellowellow') 
print master 

Answer 1

można zrobić coś takiego:.

tgt='helloyellowellow' 

with open('/usr/share/dict/words') as f: 
    for word in f: 
     word=word.strip() 
     if word in tgt and len(word)>1: 
      print word 

Drukuje:

el 
ell 
he 
hell 
hello 
lo 
low 
loy 
ow 
owe 
we 
well 
ye 
yell 
yellow 

Jeśli tylko szukasz funkcji is_word że niezdefiniowane, można bawić się z czymś takim:

def is_word(word, dic='/usr/share/dict/words'): 
    if not hasattr(is_word, 'words'): 
     with open(dic) as f: 
      is_word.words={word.strip() for word in f} 

    return word in is_word.words and len(word)>1 

Jako domyślną strukturę danych, zestawy Python mają średnią look-up time of O(1). Jest bardzo mało prawdopodobne, aby napisać coś na własną rękę, co jest szybsze.

Answer 2

Dobrze problem rozwiązać z,

Zastosowanie Wordnet pakiet,

podczas parsowania Twój dany ciąg początek jakiegoś indeksu i utrzymać dręczyć swoją wartość indeksu dla każdego przyrostowego na indeksie, należy sprawdzić istnienie to samo słowo, używając wordnetu, powie ci, że konkretny pod-łańcuch jest znaczący, czy nie!

Aby zainstalować wordnet:

https://pypi.python.org/pypi/Wordnet-bn/1.0 

Answer 3

Skoro wspomniałeś szukasz wydajnego algorytmu, i zakładając, masz słownika z góry (i to nie tylko jako na żądanie orzecznika), można użyć Aho–Corasick algorytm.

Oczywiście, jeśli tekst wejściowy jest krótki, bardziej naiwny algorytm będzie szybszy, aby uniknąć "kosztownego" wstępnego przetwarzania słownika.

Plus, alternatywą python-odpowiedź: oto prosty sposób, aby po prostu sprawdzić każdy podciąg:

def gen_words(txt): 
    n = len(txt) 
    for i in range(n): 
     for j in range(i+1, n+1): 
      subtxt = txt[i:j] 
      if is_word(subtxt): 
       yield subtxt 

niepowtarzalności, zrobić:

all_words = set(gen_words(txt))