История изменений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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