LINUX.ORG.RU
Форум — Development  

Посоветуйте алгоритм разбора строки.


0

0
Есть строка. Есть список X из списков Yi. Нужно разобрать строку, как это делают регеспы, но в качестве шаблона служат элементы списка Yi, входящего в X. То есть шаблон для строки pattern1 pattern2..., где patterni - список Yi. Возможно существование нескольких вариантов разбора. Нужен наиболее быстрый алгоритм. Пока есть идеи насчёт "образовать и проверить", может на его основе что-нибудь есть, учитывающий потенциальные грабли?
anonymous
← GD - gd_info() выдает что Freetype не поддерживается
[C++]Структуры. →
Если Yi — это строки (списки символов), то проще всего сделать регексп (Y1)|(Y2)|(Y3)|...|(Yn). Если Yi — просто списки элементов (а не шаблоны в смысле регэкспов), то можно воспользоваться алгоритмом Ахо-Корасика.
mo3r
() 
Пример приведи.
Из того, что мне удалось понять, могу предложить такой вариант:
((Y1_1) | (Y1_2) | ... | (Y1_N))((Y2_1) | (Y2_2) | ... | (Y2_N))...((YM_1) | (YM_2) | ... | (YM_N))
Legioner ★★★★★
()
Ответ на: комментарий от Legioner
>Пример приведи.

Например, разбор слова по составу. Есть префикс, корень, интерфикс, суффикс и флексия. Из-за омонимии возможно несколько вариантов разбора. Каждая часть может отсутствовать, а может присутствовать несколько раз (пара суффиксов, к примеру). Ну а если алгоритм сможет разобрать и циркумфикс, будет вообще замечательно.

>Из того, что мне удалось понять, могу предложить такой вариант: ((Y1_1) | (Y1_2) | ... | (Y1_N))((Y2_1) | (Y2_2) | ... | (Y2_N))...((YM_1) | (YM_2) | ... | (YM_N))

Пробовал, не то. При большом количестве вариантов (более 17 тыс) обычные регеспы просто не работают, а grep, к примеру, захавал гиг оперативки при таком "шаблоне" на одном слове и не справился за несколько минут.

Алгоритм аля прологовский бактракинг тоже не катит - очень неэффективный.

anonymous
()
Ответ на: комментарий от mo3r
>то можно воспользоваться алгоритмом Ахо-Корасика.

Да, на первый взгляд, то, что нужно. Сенкс.

anonymous
()
Ответ на: комментарий от anonymous
> Пробовал, не то. При большом количестве вариантов (более 17 тыс) обычные регеспы просто не работают

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

Legioner ★★★★★
()
Ответ на: комментарий от Legioner
А есть ли ч-либо (программа/алгоритм) для построения конечных автоматов по шаблонам? То есть на входе - список допустимых строк, алфавит, термальные и нетермальные символы, а на выходе - готовый автомат?
anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← GD - gd_info() выдает что Freetype не поддерживается
Development
[C++]Структуры. →