самый эффективный алгоритм для разделения слов?

Question

Я искал эффективный алгоритм разделения слов, но без особого успеха. Например, учитывая слово привет, я хочу получить все возможные разделы этого слова: {h, e, l, l, o}, {h, e, l, lo}, {h, e, llo} ,. ..,{Привет}. Все, что я нашел, говорит о разделении слов, что я не имею в виду.

Заранее спасибо!

Answer 1

Вы показываете несколько примеров, где мы можем сосредоточиться на запятых.Либо есть запятая, либо нет.

 Word        Commas
{h,e,l,l,o}  1111
{h,e,l,l o}  1110
{h,e,l l o}  1100
...
{h e l l o}  0000

Так что очевидно, что на 4 позициях может быть запятая или нет, независимо друг от друга.Вам нужно 4 бита для кодирования разделов, что составляет 2 ^ 4 возможностей, я думаю, это 16.

Таким образом, вы можете сформировать цикл:

for (int i = 0; i < 15; ++i)
    bitsplit ("hello", i);

и перебирать свое слово, покаперебирая биты двоичного представления i.Например, для 11 у вас есть биты: 8 + 2 + 1 = 1011.Это значит {ч, эл, л, о}.

Answer 2

Проблема в том, что NP завершена, и ее необходимо решить путем возврата.

Идея заключается в том, чтобы на каждом уровне вы решали, принадлежит ли этот персонаж текущему разделу или перейти на новый. Делайте это рекурсивно, и каждый раз, когда вы достигаете конца слова, у вас есть один раздел.

Answer 3

Скорее всего, вы хотите построить суффикс-три.