Проверка возможности сегментации слов

Это дополнительный вопрос к этот ответ и алгоритм псевдокода, опубликованный пользователем. Я не комментировал этот вопрос из-за его возраста. Меня интересует только проверка того, можно ли разбить строку на слова. Алгоритму не нужно на самом деле разбивать строку. Это ответ на связанный вопрос:

Пусть S[1..length(w)] — таблица с булевыми записями. S[i] истинно, если слово w[1..i] можно разделить. Затем установите S[1] = isWord(w[1]) и для i=2 до length(w) вычислите

S[i] = (isWord[w[1..i] или для любого j в {2..i}: S[j-1] и isWord[j..i]).

Я перевожу этот алгоритм в простой код Python, но я не уверен, правильно ли я его понимаю. Код:

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, str_len):
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

У меня есть два связанных вопроса. 1) Является ли этот код правильным переводом связанного алгоритма на Python, и если это так, 2) Теперь, когда у меня есть S, как мне использовать его, чтобы определить, состоит ли строка только из слов ? В данном случае is_word — это функция, которая просто ищет заданное слово в списке. Я еще не реализовал это как попытку.

ОБНОВЛЕНИЕ: после обновления кода для включения предложенного изменения он не работает. Это обновленный код:

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, i): #THIS LINE WAS UPDATED
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

a_string = "carrotforever"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints FALSE

a_string = "hello"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints TRUE

Он должен вернуть True для обоих из них.


python nlp algorithm dynamic-programming text-segmentation
person Ricardo Altamirano    schedule 22.04.2012    source источник
comment
Вы когда-нибудь заставляли это работать?   -  person thinkdevcode    schedule 14.08.2012
comment
@thinkdevcode Да. См. мой комментарий к принятому ответу.   -  person Ricardo Altamirano    schedule 14.08.2012

Ответы (3)


arrow_upward
2
arrow_downward

Вот модифицированная версия вашего кода, которая должна возвращать хорошие результаты. Обратите внимание, что ваша ошибка заключалась просто в переводе из индексации массива псевдокода (начиная с 1) в индексацию массива python (начиная с 0), поэтому S[0] и S[1] заполняются тем же значением, что и S[L-1] фактически никогда не вычислялся. Вы можете легко отследить эту ошибку, напечатав все значения S. Вы обнаружите, что S[3] установлено как true в первом примере, где должно быть S[2] для слова "автомобиль". Также вы можете ускорить процесс, сохранив индекс составных слов, найденных до сих пор, вместо проверки каждой позиции.

def is_all_words(a_string, dictionary):
    str_len = len(a_string)
    S = [False] * (str_len)
# I replaced is_word function by a simple list lookup, 
# feel free to replace it with whatever function you use. 
# tries or suffix tree are best for this.
    S[0] = (a_string[0] in dictionary) 
    for i in range(1, str_len):
        check = a_string[0:i+1] in dictionary # i+1 instead of i
        if (check):
            S[i] = check
    else:
        for j in range(0,i+1): # i+1 instead of i
            if (S[j-1] and (a_string[j:i+1] in dictionary)): # i+1 instead of i
            S[i] = True
            break


    return S

a_string = "carrotforever"
S = is_all_words(a_string, ["a","car","carrot","for","eve","forever"])
print(S[len(a_string)-1]) #prints TRUE

a_string = "helloworld"
S = is_all_words(a_string, ["hello","world"])
print(S[len(a_string)-1]) #prints TRUE
person Samy Arous    schedule 23.04.2012
comment
Спасибо вам за помощь. Этот код работает. Я исправил ошибки в ваших операторах печати (окончание ] отсутствовало, поэтому последняя строка выглядит так: print(S[len(a_string)-1])) и добавил свою привычную функцию словаря, и похоже, что она работает. - person Ricardo Altamirano; 26.04.2012

arrow_upward
2
arrow_downward

Реальный пример сегментации английских слов можно найти в источнике модуля Pythonwordsegment< /а>. Он немного сложнее, потому что использует таблицы частоты слов и фраз, но иллюстрирует рекурсивный подход. Изменив функцию score, вы можете расставить приоритеты для более длинных совпадений.

Установка проста с pip:

$ pip install wordsegment

И segment возвращает список слов:

>>> import wordsegment
>>> wordsegment.segment('carrotfever')
['carrot', 'forever']
person GrantJ    schedule 02.09.2015
comment
Привет @GrantJ, я использую ваш пакет Python word segment. Это превосходно. Хотя он отлично работает для текста, включающего только текст, он не работает должным образом, как только в тексте появляется число. Например, следующий текст: joined the habit in 2008, after karpreilly, a private investment превращается в ['joined', 'the', 'habit', 'in2008afterkarp', 'reilly', 'a', 'private', 'investment']. Знаете ли вы, есть ли способ решить проблему, когда речь идет о числах? Спасибо - person Saurabh Gokhale; 29.11.2018
comment
Точно сказать не могу. Можете ли вы открыть вопрос GitHub? - person GrantJ; 30.11.2018

arrow_upward
1
arrow_downward

1) на первый взгляд выглядит хорошо. Одна вещь: for j in range(1, str_len): должно быть for j in range(1, i): я думаю

2) если S[str_len-1]==true, то вся строка должна состоять только из целых слов.

Ведь S[i] истинно тогда и только тогда, когда

  • вся строка от 0 до i состоит из одного словарного слова
  • ИЛИ существует S[j-1]==true с j<i, а строка[j:i] является одним словарным словом

поэтому, если S[str_len-1] истинно, то вся строка состоит из словарных слов

person HugoRune    schedule 22.04.2012
comment
Я обновил свой вопрос, потому что алгоритм все еще не возвращает правильное решение. - person Ricardo Altamirano; 23.04.2012