Как разбить текст на слова?

В общем случае никак.

Язык, на котором написаны слова, не важен

Важен.

Также нужна устойчивость к опечаткам

Тем более.

Покопайся среди набора питоновских библиотек NLTK. Может найдёшь под твой случай подходящие модули. Но идеального решения там заведомо не будет.

тестовые задания.

Язык, на котором написаны слова, не важен. Язык программирования тоже неважен.

Функция на перле для китайского языка:

sub get_words($) {
    my ( $text ) = @_;
    return ( $text );
};

Дарю.

А нет ощущения, что слишком много взаимоисключающих требований?)

Нет, не кажется, зайти в гугл переводчик и проверь

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

Кажется*

без использования нейросетей

гугл переводчик

нужно это сделать без использования нейросетей

September 2016: Google announced Google Neural Machine Translation (GNMT), an 8-layer LSTM network with attention that cut translation errors by ~60 %.

In 2017 Google migrated GNMT to the Transformer architecture, the same architecture that underpins modern LLMs, boosting both quality and speed.

Да, до этого было без невросетей, но не помню, чтобы там прям могло по словам разбить

Если words = [в, ведро], s = ведро, то получишь бесконечный цикл и неправильный результат

N-граммы?

Начнем с ослова «therapist».

Проверь на примере «шлакоблокунь».

Язык, на котором написаны слова, не важен.

Фигня получится, если не важен. Язык важен и понадобится полный анализ фразы. Иначе понаразбиваешь всякий «шестик анальный», «в роде», «бур — да!», «то вар», а «та бор», «конь як», «мышь як» и «пуст як» (бедный як…) а если всякие не совсем литературные слова тоже допустимы, то и «чел овечий». Ну а если ещё и опечатки допустимы, то ещё и «опер упал намоченный» получится.

https://www.youtube.com/watch?v=GB5dmv9WYVY

Берете любую простую библиотку для разбивки, например вот эту и заменяете словарь английских слов на словарь русских слов.

Если нужно разобраться как это работает то открываете и читаете комментарии в коде. Там всего кода не больше 50 строк.

Очевидно напрашивается trie с входными словами.

Базовый алгоритм - матчить по нему самое длинное слово из словаря, потом начинать матчить следующее. Работает супер быстро за O(N) и работает с байтами, поэтому язык не важен, не умеет в опечатки и в слова являющиеся префиксами других слов. Может сойти как частное решение, формы слов с опечатками можно также добавить в словарь, но префиксы никак не обойти.

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

• Матчим по trie все варианты, а не самый длинный, откладываем в priority queue по общему размеру сматченного чтобы работало жадно и меньше буксовало на коротких словах типа предлогов и союзов. Префиксы побеждены.
• Матчим с учётом опечаток, с trie это просто, но тут может получаться очень много комбинаций. Стоит ограничить частоту опечаток и ускорить приоретизируя варианты без опечаток. И использовать модель опечаток, скорее всего такую можно где-то найти, учитывающую не произвольную замену/пропуск/добавление буквы, а наиболее вероятные опечатки из-за близости клавиш или статистику полученную из настоящих набранных текстов.
• Понятно что в какой-то момент нужно сдаваться чтобы не тратить слишком много времени, и не генерить слишком много вариантов.

Да, шестиканальный гугл-переводчик понял, а вот опечатки (оперупал намоченный -> operatedwettedit will work out) неосилил. :)

Да и полный анализ не поможет, вон гугл переводчик упорно считает «коньякичеловек» -> «cognacsman»...

Простое решение здесь не сработает. Наличия словаря не гарантирует точную разбивку на слова. Обязательно возникнет непредвиденное сходство, например «этопросто» и «топ» будут обрабатывать «топ» два раза.

$words = "это","пример","массива","топ","100","слов","текста"
$str = "этопримертекста"
$pattern = $words -join '|'
$str -split "(?<=$pattern)(?!$)"

это
п
ример
текста

Но если «топ» заменить на «топовых», то ошибки не возникнет.

Задача нерешаема в общем случае, так как один и тот же набор букв может иметь несколько валидных разбиений на слова (как уже привели пример therapist).

Непонятно как эти противоречия разрешать.

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

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

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

Что касается наивного алгоритма со словарём, тебе не нужно смотреть на все слова текста. Так как слова имеют ограниченную длину (и в 99% случаев эта длина на порядки меньше длины целого текста), а чем длиннее слово, тем меньше у него коллизий с другими. Плюс сами слова в тексте влияют на смысл друг-друга слабее, если расположены далеко (во всяком случае НАСТОЛЬКО влияют, чтобы менять разбиение, так как тексты устроены таким образом, что их можно понимать по мере чтения не заглядывая вперёд). Для определения слова можно смотреть на несколько десятков следующих букв даже если мы парсим «Войну и мир» (для универсальности можно взять N * длину самого длинного слова в словаре, где N, например, равно 5 для начала).

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

Заполируем сайтом свалко.орг. Конипони, надо зайти в комменты к пстам.

Начнем

наполеонкосилтраву

полякипелисоловьём

1. нужен словарь популярных слов.
2. находим все слова в тексте разделенные пробелами и знаками препинания.
3. во всех найденных словах ищем популярные слова.

Как разбить текст на слова?

Мэйнстрим салюшен:

Регаешь гопоту, пишешь промт. Тащишь клиента к апи гопоты, подсовываешь свой рег и промт. Пакуешь клиента в докер. Докер в прод.

Работать будет. Плюс-минус )

Никак, это предсказуемо для произвольного языка и его слов сделать невозможно в принципе (да?), так как ты прямо сейчас можешь начать словообразование таких слов которых не существует, но они по всем паравилам и тд про шлакоблокуня и чело века уже сказали, хрен тебя знает как кой вариант ты будешь считать верным, ладно ты, а другой?. Только разве что с набором из белого списка слов получится. Всё что не удалось разбить и чего нет в словаре, пытаемся рассматривать как слово с опечаткой, ищем вхождение частей, до наиболее длинного, и либо приводим до нужного применив Nmax замен, или/и если не получилось просто оставляем как есть, аля тут тарабарщина. А если есть белый список слов то можно вообще в дерево засунуть и искать самое длинное по совпадению O(Log2) и дело в шляпе. Но шаг в сторону и каюк, вернее додумывать неразрешённые случаи например может человек исходя из своего субъективного мнения и настроения :)

Но это просто мысли в слух, я в этом никак не разбираюсь.

Тут теория вероятностей нужна

Я подобныое видел только в IME типа Mozc/Anthy когда надо японский превратить в слова и без нейросетки, одним лишь движком распознавания. Ну или сам догадывайся почему у них все слитно пишется во фразе вида АНАТАВАДОКОНОКУНИКАРАКИМАЩИТАКА.

1. Собираешь базу слов и их склонений для каждого языка (включая частотные таблицы)
2. Собирает частотные таблицы символов для каждого языка
3. Детектишь язык по частотным таблицам из 1 и 2
4. Разбиваешь текст на основе таблиц из 1

Зашёл, забил «wdymuhavenobbq?», он ничё не понял.

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

Наверное потому что у нас барбекю называют шашлыками?

Нет, вряд ли. Скорее всего из-за того что задача в общем виде нерешаемая.

Literally me

Но ты же в голове как-то разбил.

Спасибо, попробую trio и ещё както буду проверять падежи. Просто я хотел сделать парсер человеческого языка без нейросетей. Я понимаю, что на создание парсера даже самых простых фраз уйдут годы, просто мне нехуй делать

Тогда не частотный словарь слов, а частотный словарь словосочетанй по два-пять слов. Их больше, но распознавать будет лучше.

Язык, на котором написаны слова, не важен

Расскажи это языкам где нет пробелов между словами

Начнем с ослова «therapist».

У кого что болит… А кто такой Ослов? Это фамилия терапевта-насильника?

Только человек может так тонко чувствовать контекст.

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

Элементарно: делаем порносайт, а к нему капчу — задачку на разбиение текста на слова.

Идеальный кейс для нейросети - когда ты некомпетентен и не можешь придумать алгоритмического решения. Тут решений достаточно накидали, попробуй сделать лучше сеткой. По доброте душевной даю тебе на это даже 2x CPU time и 2x времени на обучение.

Элементарно:
комбиринуешь все подстроки из текста «этопримертекста», и для каждой такой подстроки запоминаешь позицию в тексте и генерируешь последовательности строк из сгенерированных подстрок текста, разделенных пробелом и с учётом позиции (по возрастанию), т.е. разбиение текста. Если почти все (и тем более все) подстроки станут осмысленными (валидными словоформами), то разбиение можно считать найденным.

Валидные словоформы ищутся или в особых словарях, или генерируется самостоятельно частотный словарь словоформ Войны и Мира, убрав всё французское, латинское и цифры, прочие нерелевантные знаки.

задача сводится к дописанию в бойера-муера алгоритма устойчивости к опечаткам или «иной желаемой эвристики» :)
а это совсем другая история… (c) каневский

дописанию в бойера-муера алгоритма устойчивости к опечаткам

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

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

Компетентный ты наш, тут накидали достаточно примеров, на которых алгоритмические решения спотыкаются из-за неоднозначности в них разбиения на слова.

Конечно, если разбиение с такими ошибками устраивает, то зачем городить лишние сложности там, где управится код в 50 строчек.

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

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

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

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

Задача нерешаема в общем случае, так как один и тот же набор букв может иметь несколько валидных разбиений на слова

Для упрощения можно использовать только топ-100 или топ-1000 самых популярных слов. - по условию задачи у нас есть четкий набор слов которые нужно находить. Мы не решаем задачу в общем случае.

Универсального алгоритма для всех языков тоже нельзя сделать

Есть условие задачи. Там четкое ограничение на топ-100 или топ 1000. Причем тут разные языки?

Лучше всего тут как раз подойдут нейросети, потому что, во-первых,

Во-первых: Также нужно это сделать без использования нейросетей - по условию задачи.

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