Алгоритм разбивки «сплошного» текста на слова

google CJK segmentation?

Какой ужас! =O

Найми 1*10^6 индо-китайцев, за тарелку риса они это сделают и еще чего нить напишут.

Похоже на алгоритм лемпела-зива, который при архивировании используется. Там как раз поиск частот встречаемости строк, построение словаря на ходу и генерация сжатой последовательности. Только тебе не последовательность нужна будет, а сам словарь, получившийся в конце.

>> Похоже на алгоритм лемпела-зива, который при архивировании используется. Там как раз поиск частот встречаемости строк, построение словаря на ходу и генерация сжатой последовательности. Только тебе не последовательность нужна будет, а сам словарь, получившийся в конце.

Тоже такая мысль в голову пришла.

>> google CJK segmentation?

Я правильно понял что это что-то для китайских текстов?

> Я правильно понял что это что-то для китайских текстов?

А Вам для какого языка надо ?

>> А Вам для какого языка надо ?

Не для какого. В том то и фокус, что язык не известен. Может это будет русский, может китайский, а может исходник на перле. Кодировка тоже неизвестна.

Есть такая вещь, как «Minimum description length principle». Идея заключается в том, что ищется такое описание объекта (в данном случае — набор байтов), которое имеет минимальную длину (например, за длину можно взять длину словаря + количество слов). Правда, конкретный алгоритм, реализующий эту идею, не знаю.

Я правильно понимаю, вы не знаете как вычленить слова из текста?

Потому что такое проходят на первом курсе не то что в вузах - в любом провинциальном ПТУ.

> Потому что такое проходят на первом курсе не то что в вузах - в любом провинциальном ПТУ.

ラドクリフ、マラソン五輪代表に１万ｍ出場にも含み

ну вычлени мне тут слова...

И что, без пробелов? Шютник.

>> Я правильно понимаю, вы не знаете как вычленить слова из текста?

>> Потому что такое проходят на первом курсе не то что в вузах - в любом провинциальном ПТУ.

ядействительнонезнаюкаквычленитьсловаизтакоговоттекстатемболеечтониязыкни кодировканеизвестныиихневозможноопределитьсоответственнозаранеезаготовленныйсло варьтожеиспользоватьневозможно

>> И что, без пробелов? Шютник.

Текст конечно же с пробелами. Но только байт с каким кодом обозначает пробел - неизвестно.

>> google CJK segmentation?

> Я правильно понял что это что-то для китайских текстов?

это задача, наподобие описанной в этом треде, но вполне конкретная:
в ряде языков (китайский, японский, корейский) не исользуются пробелы
при этом нужно как-то уметь разбивать текст на слова -- например для
индексации и поиска.

разными способами это научились делать, более-менее успешно.

Если же речь идет о "ни о каком" языке, то непонятно как оценивать результат.
Потому что для реального языка можно сказать, насколько точно текст
был разбит на слова. Если же про язык не известно ничего -- надо
вводить какой-то иной критерий оценки, например минимизаци энтропии,
как предложили выше.

> кодировканеизвестныиихневозможноопределитьсоответственн
> озаранеезаготовленныйсловарьтожеиспользоватьневозможно

а как насчет

14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196
44288109756659334461284756482337867831652712019091
45648566923460348610454326648213393607260249141273 ?

Из такого текста - в общем случае никак. Даже со словарем, даже с однобайтовыми кодировками. Потому, что однозначно определить слово нельзя, никаких свойств префиксности в естественных языках не соблюдается. Разве что, полагаясь на то, что текст составлен грамматически правильно, находить определенные фрагменты слова, такие как окончания и т.д, но и то слабо поможет - вероятность спутать, опять же, огромная.

> И что, без пробелов? Шютник.

мир не ограничивается Вашим ПТУ и есть языки с письмом без пробелов, есть даже с записью цифр не арабскими и не римскими символами, есть где пишут с право на лево, есть где пишут сверху вниз... удивительно правда ? :)

Для произвольного языка это тем более невозможно.
По крайней мере, на машине Тьюринга.

Где в лемпель-зиве поиск частот?

Боюсь, что при такой постановке задачи слишком высок шанс, что "о" окажется знаком пробела, а "ться" и "вый" окажутся "словами".

P.S. В тексте моего сообщении 29 букв "о" и 20 пробелов.

Для простых языков составить "словарик(и)" из наиболее распространенных "пробелов", возможно определять кодировку и язык по ней, и в зависимости от языка использовать нужный словарь, а вот со сложными... Как будем разделять "словообразующий"? Или иероглифы, где разные последовательности образуют разные слова? Т.е. "abcabc" != "abc" + "abc", а скорее "ab" + "ca" + "bc". Имхо, без знания конкретного языка тут никуда. Нам нужен разделитель, хотя самим языком он может быть не предусмотрен.

составить частотный словарь слогов. Кластеризовать частоты по входимости в приставки/корни/суффиксы/окончания (то есть, вероятность вхождения одного и того же слога в приставки или окончания -- разная). Написать парсер, который подбирает наиболее вероятные элементы, соблюдая последовательность элементов (то есть, ловить окончания/приставки = конец старого слова, начало нового).

> Текст конечно же с пробелами. Но только байт с каким кодом обозначает пробел - неизвестно.

тогда фигня вопрос. Частота вхождения разных букв в текст в разных языках разная, но в целом у гласных больше, у согласных меньше (если гласные вообще пишутся). А у пробелов должна быть ещё больше.

Кстати, есть еще одна вешь - решение типа "словосочетание" vs "слово сочетание" невозможно принять без понимания контекса.

>> Кстати, есть еще одна вешь - решение типа "словосочетание" vs "слово сочетание" невозможно принять без понимания контекса.

Даже если слова "слово" и "сочетание" встречаются также и поотдельности?

>> Кстати, есть еще одна вешь - решение типа "словосочетание" vs "слово сочетание" невозможно принять без понимания контекса.

>Даже если слова "слово" и "сочетание" встречаются также и поотдельности?

Ну какбе программа при разбивке должна понимать что есть не только слова "слово" и "сочетание" но и цельное слово "словосочетание". Так что простой жадный алгоритм не прокатит. Нужна эвристика, которая тем не менее 100% корректности дать не может.

> Нужна эвристика, которая тем не менее 100% корректности дать не может.

сперва нужна постановка задачи корректная, а её почему-то ОП выдать так и не удосужился

>> Нужна эвристика, которая тем не менее 100% корректности дать не может.

>сперва нужна постановка задачи корректная, а её почему-то ОП выдать так и не удосужился

Ну так поставь, ёмаё. По постингу понятно чего автор хочет - он хочет разбить текст по словам.

>Кстати, есть еще одна вешь - решение типа "словосочетание" vs "слово сочетание" невозможно принять без понимания контекса

не говоря уже о том, что в общем случае текст может содержать опечатки и "олбанский".

В общем случае язык представляет собой конечное множество цепочек символов алфавита (слов). Алфавит тоже представляет собой конечное множество.

В случае, когда имеется некоторая последовательность символов, из нее представляется возможным выделить только алфавит, или, в общем случае, некоторое его подмножество. Слова выделить не получится по следующим соображениям:

1. Вся цепочка может являтся одним словом.

2. Слово может включать в себя повторяющиеся последовательности. Например, слово "мимикрия" включает в себя повторяющийся фрагмент "ми". Это в общем случае не позволяет разделить повторяюшиеся цепочки на слова(так как это могут быть слоги или устойчивые фразеологизмы)

В случае, если имеется лишь последовательность байтов, не получится выделить даже алфавит (см. многобайтные кодировки)

А вообще полезно будет почитать "Введение в теорию автоматов, языков и вычислений" Джона Хопкрофта.

В общем уже не нужно. Кажется меня отпустила эта бредовая идея...

> По постингу понятно чего автор хочет - он хочет разбить текст по словам.

имхо он хочет чтобы в жопе перестало чесаться а не текст по словам

Забудьте про байты, поцаны.

Всё гораздо хуже.

http://local.joelonsoftware.com/wiki/%D0%90%D0%B1%D1%81%D0%BE%D0%BB%D1%8E%D1%...

> Забудьте про байты, поцаны.
> Всё гораздо хуже.

Мы все умрем?
В данной задаче никто не мешает представлять двухбайтовый символ как два символа.

> Мы все умрем?

а как же

Wikipedia lists the longest word as Töredezettségmentesítőtleníttethetetlenségtelenítőtlenkedhetnétek meaning "you [plural] could constantly mention the lack [of a thing] that makes it impossible to make someone make something defragmenter-free".

(Hungarian)