Как я могу рекурсивно генерировать несколько слов?

Question

Скажите, у меня есть строка слов: 'a b c d e f'. Я хочу сгенерировать список терминов из нескольких слов из этой строки.

Порядок слов имеет значение. Термин 'f e d' не должен генерироваться из приведенного выше примера.

Редактировать: Кроме того, слова не должны быть пропущены. 'a c' или 'b d f' не должны генерироваться.

Что у меня сейчас есть:

doc = 'a b c d e f'
terms= []
one_before = None
two_before = None
for word in doc.split(None):
    terms.append(word)
    if one_before:
        terms.append(' '.join([one_before, word]))
    if two_before:
        terms.append(' '.join([two_before, one_before, word]))
    two_before = one_before
    one_before = word

for term in terms:
    print term

Печать:

a
b
a b
c
b c
a b c
d
c d
b c d
e
d e
c d e
f
e f
d e f

Как бы я сделал эту рекурсивную функцию, чтобы я мог передать ей переменное максимальное количество слов за термин?

Применение:

Я буду использовать это для создания многословных терминов из читаемого текста в документах HTML. Общая цель - скрытый семантический анализ большого корпуса (около двух миллионов документов). Вот почему поддержание порядка слов имеет значение (обработка естественного языка и еще много чего).

Answer 1

Это не рекурсивно, но я думаю, что оно делает то, что вы хотите.

doc = 'a b c d e f'
words = doc.split(None)
max = 3          


for index in xrange(len(words)):    
    for n in xrange(max):
        if index + n < len(words):           
            print ' '.join(words[index:index+n+1])   

А вот рекурсивное решение:

def find_terms(words, max_words_per_term):       
    if len(words) == 0: return []
    return [" ".join(words[:i+1]) for i in xrange(min(len(words), max_words_per_term))] + find_terms(words[1:], max_words_per_term)


doc = 'a b c d e f'
words = doc.split(None) 
for term in find_terms(words, 3):
    print term

Вот снова рекурсивная функция с некоторыми поясняющими переменными и комментариями.

def find_terms(words, max_words_per_term):   

    # If there are no words, you've reached the end. Stop.    
    if len(words) == 0:
        return []      

    # What's the max term length you could generate from the remaining 
    # words? It's the lesser of max_words_per_term and how many words 
    # you have left.                                                         
    max_term_len = min(len(words), max_words_per_term)       

    # Find all the terms that start with the first word.
    initial_terms = [" ".join(words[:i+1]) for i in xrange(max_term_len)]

    # Here's the recursion. Find all of the terms in the list 
    # of all but the first word.
    other_terms = find_terms(words[1:], max_words_per_term)

    # Now put the two lists of terms together to get the answer.
    return initial_terms + other_terms 

Answer 2

Почему ты это делаешь? Вместо этого вы можете просто использовать цикл for и itertools.combinations().

Answer 3

Я бы посоветовал вам сделать свою функцию генератором, а затем сгенерировать необходимое количество терминов. Вам нужно изменить print на yield (и, очевидно, сделать весь блок функцией).

Вы также можете взглянуть на модуль itertools , он довольно полезен для выполняемой вами работы.

Answer 4

То, что вы ищете, это N-граммовый алгоритм. Это даст вам [a, ab, b, bc, c, cd, ...].