Greedy podejście korzystania trie
Spróbuj używając Biopython (pip install biopython):
from Bio import trie
import string
def get_trie(dictfile='/usr/share/dict/american-english'):
tr = trie.trie()
with open(dictfile) as f:
for line in f:
word = line.rstrip()
try:
word = word.encode(encoding='ascii', errors='ignore')
tr[word] = len(word)
assert tr.has_key(word), "Missing %s" % word
except UnicodeDecodeError:
pass
return tr
def get_trie_word(tr, s):
for end in reversed(range(len(s))):
word = s[:end + 1]
if tr.has_key(word):
return word, s[end + 1: ]
return None, s
def main(s):
tr = get_trie()
while s:
word, s = get_trie_word(tr, s)
print word
if __name__ == '__main__':
s = "Imageclassificationmethodscan beroughlydividedinto two broad families of approaches:"
s = s.strip(string.punctuation)
s = s.replace(" ", '')
s = s.lower()
main(s)
Wyniki
>>> if __name__ == '__main__':
... s = "Imageclassificationmethodscan beroughlydividedinto two broad families of approaches:"
... s = s.strip(string.punctuation)
... s = s.replace(" ", '')
... s = s.lower()
... main(s)
...
image
classification
methods
can
be
roughly
divided
into
two
broad
families
of
approaches
Ostrzeżenia
Istnieje zdegenerowane przypadki w języku angielskim, że to nie będzie pracować dla. Aby sobie z nimi poradzić, musisz użyć funkcji cofania, ale powinno to zacząć.
obowiązkowe testy
>>> main("expertsexchange")
experts
exchange
Możesz zakodować słownik słów jako trie i użyć chciwego algorytmu: wyciągnij najdłuższe słowo, które pasuje, a następnie przejdź do następnego słowa, wycofując się z błędu. Prawdopodobnie nie jest optymalna. Wypróbuj zalecenia dotyczące struktur danych: http://kmike.ru/python-data-structures/ – hughdbrown
Interesujące pytanie. Domyślam się, że odpowiedź ("łatwa droga") będzie "nie". –
Podobne pytanie wcześniej nie miało szczęścia: http://stackoverflow.com/questions/13034330/how-to-separate-an-engilsh-language-string-without-space-to-form-some-meaningfu –