Привет!
Подскажите, пожалуйста, наводку на наиболее приемистый алгоритм разбиения слова на заданные заранее слованые лексемы (например, слоги).

Здравствуйте, dad, Вы писали:

dad>Привет!
dad>Подскажите, пожалуйста, наводку на наиболее приемистый алгоритм разбиения слова на заданные заранее слованые лексемы (например, слоги).


имеется ввиду, что-то современное, помимо проходов с перебором слогов

Здравствуйте, dad, Вы писали:

dad>Подскажите, пожалуйста, наводку на наиболее приемистый алгоритм разбиения слова на заданные заранее слованые лексемы (например, слоги).

Заданные каким образом, перечислением?

Из любого такого перечисления можно построить регулярный конечный автомат, который разобъет слово на запчасти за время O(n), где n — длина слова.

Pzz>Из любого такого перечисления можно построить регулярный конечный автомат, который разобъет слово на запчасти за время O(n), где n — длина слова.


однопроходное разбиение на слоги? на каждую вариацию по автомату?

Здравствуйте, dad, Вы писали:

Pzz>>Из любого такого перечисления можно построить регулярный конечный автомат, который разобъет слово на запчасти за время O(n), где n — длина слова.

dad>однопроходное разбиение на слоги? на каждую вариацию по автомату?

На каждый набор слогов.

dad>>однопроходное разбиение на слоги? на каждую вариацию по автомату?

Pzz>На каждый набор слогов.

а это разве не n*k получается? (k — число вариаций)

Здравствуйте, dad, Вы писали:

Pzz>>На каждый набор слогов.

dad>а это разве не n*k получается? (k — число вариаций)

Что такое число вариаций?

Pzz>Что такое число вариаций?

набор слогов

Здравствуйте, dad, Вы писали:

Pzz>>Что такое число вариаций?

dad>набор слогов

От количества слогов время работы автомата не зависит. Но от них зависит сложность самого автомата, и время его построения. Впрочем, если просто есть сколько-то фиксированных слогов, то автомат получится несложным (хоть и развесистым, если слогов в наборе много), и построить его можно быстро.

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

zz>От количества слогов время работы автомата не зависит. Но от них зависит сложность самого автомата, и время его построения. Впрочем, если просто есть сколько-то фиксированных слогов, то автомат получится несложным (хоть и развесистым, если слогов в наборе много), и построить его можно быстро.

Pzz>P.S. Насколько я понимаю, разбор слова на слоги для русского языка не сводится к разбиению слова на запчасти из списка запчастей.


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


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


пример на пятом шаге:

лексемы: a, ab, b, bc, c
строка: aabbbcc

a a b b b c
a a b b bc

a ab b b b с
a ab b b bс

a a b b b c

Здравствуйте, dad, Вы писали:

dad>грамматика и не нужна. есть подстроки, есть строка да.
dad>построение автомата — с этим наверно regexp с jit неплохо справляется.

regexp с этим довольно плохо, на самом деле, справляется. Но у него и цели несколько другие, несколько выходящие за пределы того, что могут сделать регулярные автоматы в чистом виде.

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

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

Pzz>Если грамматика задана просто перечислением возможных лексем, это тривиальный случай.

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