Структура данных для представления DFA

Мне было интересно, какова была бы лучшая структура данных для представления DFA?Структура данных для представления DFA

Я рассматриваю преобразование регулярного выражения в DFA и делает эту конкретную функциональность библиотекой в Java.

Главное, что каждый объект в регулярном выражении несет в себе набор значений, а не одно значение строки, например «автомобиль». В моем случае каждый объект будет иметь много свойств, таких как {car, Honda, 4x4, седан, ...} (Хотя я не ищу автомобили, это просто пример.)

Любые предложения?

источник

2010-10-12 bsoundra

Разве это не то, что уже имеет библиотека регулярных выражений? – JoshD

JFlap делает это. Проверьте их работу. http://www.cs.duke.edu/csed/jflap/ – Mike

@Josh: Я думаю, что регулярное выражение может обрабатывать только строковый ввод с единственным свойством. Но вход для перехода может занимать несколько значений – bsoundra

Если я правильно понял ваш вопрос, вы хотите иметь библиотеку соответствия/фильтрации для произвольного регулярного языка над алфавитом с динамическими типами? Подойдя к примеру с вашим автомобилем, я бы предположил, что вы хотите создать выражение для соответствия над списком, где все автомобили (имеют красный цвет, имеют от 2 до 6 пассажиров и каждый пассажир находятся между 8 и 88 лет) или (имеют 1 пассажира).

По совпадению, я искал что-то подобное (для подтверждения документов), и ближе всего я мог получить Jing; Библиотека Java RELAX-NG. К сожалению, алфавит в Jing состоит из узлов XML, поэтому он не решил мою проблему. На данный момент я пытаюсь самостоятельно написать библиотеку, которая делает именно это (сопоставление с обычными языками над произвольным типом алфавита), основываясь на сопоставлении шаблонов в Цзин. Если вы хотите помочь в этом, пожалуйста, дайте мне знать;).

источник

2010-10-12 14:59:53 hakvroot

Я не уверен, правильно ли получил ваше объяснение. Фактически документ содержит только слово «автомобиль». Но есть связанные с ним объекты под названием Annotations. Таким образом, автомобиль аннотируется как «Автомобиль» Так что я обычно ищу тип аннотации «автомобиль», который имеет значение «автомобиль». Этот объект является первым из множества последующих объектов, который создает регулярное выражение с несколькими значениями. Под множественным значением я имею в виду, как автомобиль, являющийся типом транспортного средства. Так что я могу найти что-то вроде « продано». Это говорит об общем количестве автомобилей, проданных в доке. Это то, о чем вы говорили? – bsoundra

@bsounds: Я на самом деле не говорил с точки зрения текста, а больше с точки зрения объектов. Если вы ищете в тексте, то это действительно что-то другое;). Возможно, вы могли бы более подробно рассказать о своем случае использования? – hakvroot

Мое вложение было бы чем-то вроде «Porche продано». Это слово Porche может быть помечено как «автомобиль» или «автомобиль» или ... много других тегов. Эта информация хранится в другом объекте, связанном с файлом. Так что если я ищу «<Автомобиль, Порше> продан», то он должен найти матч. Я также могу найти «», в котором должны быть указаны все продаваемые автомобили. – bsoundra

Веб-поиск даст некоторые примеры DFA в Java. Однако наилучшее представление зависит от ваших конкретных требований к приложениям; например как ваше приложение будет использовать DFA. Думаю, вам нужно это сделать самому.

источник

2010-10-12 03:20:23

Я уверен, что этот ответ не будет полезным к первоначальному вопросу из-за данных, но если кто-то случается через это от Google ...

ДКА и НКА могут быть сохранены как State transition table's, то вы выполните синтаксический анализ, переместив мысль в таблицу, следующую за ссылками как таковыми.

источник

2011-11-03 09:22:04

Структура данных для представления DFA

ответ

Смежные вопросы