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

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

В конкретном случаи моя проблема выглядит так:
Я пытаюсь разработать морфологический анализатор предложений
У меня есть
1) Морфологический анализ каждого слова (часть речи у слова т.е. прилагательное/существительное/наречие... а так же его грамматические координаты падеж, род, число... ) в предложении.
Это есть моё дерево.
2) Правила русского языка по согласованию слов в предложении.
Это есть граф.

Пример дерева:
Есть предложение
"Очень точно". слово "очень" это наречие. А вот слово "точно" может быть как наречием, частицей и прилагательным. И мне на основе правил русского языка надо определить какой частью речи является слово "точно".

Пример узлов графа (правила русского языка):
граф состоят из узлов-условий
NameNode { существительное{ падеж:им } глагол }
Этот узел говорит, что существительное с глаголом согласуются только в том случаи если существительное только в именительном падеже.
Узлы в свою очередь вызываю другие узлы
ГруппаНареч1 { NameNode наречие{СТЕПЕНЬ:АТРИБ} }
Т.е. кагбэ происходит подстановка
ГруппаНареч1 { существительное{ падеж:им } глагол наречие{СТЕПЕНЬ:АТРИБ} }

У уже месяца полтора пытаюсь написать алгоритм а в итоге только одни костыли получаются

Мне бы хотелось услышать ваши рекомендации как можно эффективно обходит такой граф.

OOsalivanобход графа графом, звучит не логгично неправда ли?
Я с вами абсолютно согласен, звучит странновато. Понятие дерево тут не совсем конечно подходит, просто структура объекта самого предложения выглядит почти как дерево)
Но поймите и меня,
Ведь сами правила русского языка выглядят как граф. Ну таков уж с нами общий язык. С этим ничего не поделать.

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

Я на вскидку вижу два варианта для предложения "Очень точно":
1) в виде массива из
а) очень(прил.) точно(наречие)
б) очень(частица) точно(наречие)
с) очень(наречие) точно(наречие)
Но проблема в том что это очень короткое предложение, а если предложение будет из ну скажем 10 слов. Такой массив может быть из 300-500-700 элементов. И кол-во элементов в этом массиве растёт геометрически в зависимости от кол-ва слов.
Можно конечно использовать и такую структуру но она мне кажется очень затратной по памяти.

2) А можно представить в виде структуры очень похожей на дерево.
Первый уровень: Слово. (объект с полями: номер слова в базе, само слово в текстовом виде)
Второй уровень: Часть речи т.е. наречие, существительное, глагол... (объект с полями: номер части речи в базе, текстовое название части речи. )
Третий уровень: Грамматические координаты. Падеж:Существительное, Род:Муж, Лицо:1... (объект Map<Integer, Set<Integer>>, Map<CoordId, Set<CoordValues>>)

PS. Я тут по сути для того чтобы понять самую эффективную структуру и обход её.

LeonidvОткуда у вас в предложении десятки миллионов узлов?
Если вы хотите решать задачу снятия морфологической омонимии, то начните с этого:
http://download.yandex.ru/company/Zelenkov_Segalovich.pdf
Да и Вы не понял чутка, десятки миллионов узлов в правилах. Точнее базовых правил то русского языка не так уж и много (сотни). Но проблема в том, что базовые правила включают в себя другие базовые правила, а эти другие базовые правила первые правила)

Да и читал я его диссертацию, у нас два разных подхода.
Он использует вероятностные методы снятия омонимов. Чем больше база данных тем правильнее будет разбор. Там для эффективной работы нужен очень большой объема корпуса русского языка.
У меня метод основана на правилах русского языка.

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

Edd.DragonНе в том дело! Вас спрашивают, задача в чем? Чего хотите то?
Формулировка "обход графа графом" никому не понятна, т.е. не имеет смысла.
Нужно обойти объектом большой граф. Где узлы графа модифицируют поля объект.

Проблема: Первый уровень графа имеет 10 веток. После обхода первой ветки поля объекта модифицируются и когда доходит очередь до обхода второй ветки, поля у исходного объекта уже не те, что были до обхода первой ветки.
Как сохранять объект в целости, если ветка которую он обошел не подходит по условиям узлов?

PS. Делать clone() на каждом уровне не вариант, слишком много накладных расходов.

Йуный джавистЪЕсли вы имеете в виду это:
http://en.wikipedia.org/wiki/Augmented_transition_network
То есть такая книга:
http://www.paulgraham.com/onlisptext.html
Там есть код парсера естественного языка на основе континуаций.
Да очень похоже. Суть алгоритма понята, не понята реализация)

Edd.DragonЯ хз, что там у вас за особенности алгоритма.
Таки особенностей нет. Обычный граф, обходит объект. И объект модифицируются в каждом узле.

Edd.DragonМожет после модификации нужно заново начинать обход. Может наоборот, надо сначала все обойти и собрать массив модификаций, а потом уже модифицировать.
Ничего заново обходить не надо. А без самой именно модификации объекта мне не собрать массив модификаций.
Объект нужно именно изменять. Потому что условия в узлах графа смотрят на текущее состояние объект. И если состояние объекта удовлетворяет требованиям узла, узел модифицирует объект и пускает его дальше по цепочке. Если состояние объекта не удовлетворяет условиям в узле, то считаются все нижестоящие уровни не валидными.

Edd.DragonНо! Цитаты из первого сообщения:
У меня есть очень большой граф (десятков миллионов узлов) он является модификатором дерева
Если узел графа не модифицирует дерево , то ниже по графу(?) не происходит опускания.
Мне бы хотелось услышать ваши рекомендации как можно эффективно обходит такой граф(?) .
Поясните, там дерево имелось ввиду или граф,как написано?

Там ошибки нет. Замените слово дерево на объект. Мы вроде выше решили придерживаться этой терминологии.
Сам граф он стабилен, это правила русского языка. Мы применяем правила русского языка к одному предложению, методом перебора всех возможных правил русского языка.
Модификация объект выглядит по сути как "откусывание" по слову у русского предложения слева. Идёт простой перебор всех правил русского языка и попытка их применить к конкретному предложению.


Edd.DragonИ что понимается ввиду под "обойти"? Просмотреть все пары (элемент графа (правило), элемент дерева?
Да. Нужно обойти все элементы графа, объектом(деревом) модифицируя в каждом узле объект. Если модификации не происходит ветка не валидна. И дальше по ней не идёт алгоритм.

Edd.DragonЕсли так, то в общем случае, раз модификая может затронуть, что угодно и привести к необходимости модификации уже проверенных элементов уже просмотренными правилами, то значит после модификации "наша песня хороша - начинай сначала!". Или надо продумать, как иначе взглянуть на свод правил и на построение дерева предложения, чтобы отметать как можно больше заведомо ненужных проверок.
О проверенных элементах узел не может знать ничего. В этом и есть суть модификации объекта. Как я уже выше несколько раз сказал, модификация это откусывание слова у предложения. До тех пор пока предложение не станет нулевым. Если предложение стало нулевой длинны(без слов) это по сути означает что мы подобрали нужный набор правил русского языка к предложению.

Если хотите могу показать как часть правил русского языка в виде графа (но информация специфична, она далека мне кажется от понимаю человеку не в теме)

LeonidvtepkaСам граф он стабилен, это правила русского языка. Мы применяем правила русского языка к одному предложению, методом перебора всех возможных правил русского языка.

Посмотрите neo4j.

Ну например покажу два коротеньких предложения:
"очень точно"
pattern begin { НеполнПредлож }
pattern НеполнПредлож { Обст }
pattern Обст { ГруппаНареч2 }
pattern ГруппаНареч2 { ГруппаНареч1 }
pattern ГруппаНареч1 { МодифНареч наречие:*{СТЕПЕНЬ:АТРИБ} }
pattern МодифНареч { наречие:очень{} }

"иногда очень точно"
pattern begin { НеполнПредлож }
pattern НеполнПредлож { Обст }
pattern Обст { ГруппаНареч2 }
pattern ГруппаНареч2 { ГруппаНареч1 }
pattern ГруппаНареч1 { ПремодифНареч МодифНареч наречие:*{СТЕПЕНЬ:АТРИБ} }
pattern ПремодифНареч { наречие:иногда{} }

Pattern - это и есть узел графа.
То что в скобках это условия либо модификации, либо перехода к другому узлу (или группе узлов, вот например "ГруппаНареч1" это не один конкретный узел, это группа узлов состоящая из 20 штук, например есть такой узел
pattern ГруппаНареч1 { НачНаречнойГруппы_ДоПосле @or(предлог:до{},предлог:после{}) СущСРодДоп{ Падеж:РОД } } ).

Распознавалось предложение за 10-15 мс. Обойдя 5500-5700 узлов.

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

LeonidvА вообще, смотря какие методы. Можно расставить автоматически на основе словаря и обучать так. Тут, думаю, от метода зависит.

А есть у Вас, что почитать относительно методов сбора корпуса?

LeonidvЕсть возможность получить доступ к этим правилам? Я так понимаю, они у вас от научного руководителя, можно с ним связаться?

На ваш email на list.ru отправить можно контакты?

пролетевший,

Ой, спасибо большое, много идей сразу после ваших слов пришло)
Я по сути то обходил сверху. И какая то фигня получалась. Очень затратно по памяти.