Извлечение структурных элементов из Latex разметки

На днях закончил заниматься задачей извлечения структурных элементов из Latex документов. Суть в следующем:

1. Есть Latex документ.
2. Есть список структурных элементов.
3. Требуется определить вхождения элементов из списка в исходном документе.

На примере математических документов это выгляд примерно так:

1. Latex документ - научная статья из журнала или материалов конференции
2. Список структурных элементов - некоторое подмножество из онтологии OMDoc. Например, текстовые наименования таких концептов как Теорема ("theorem"), Доказательство ("proof"), Определение ("definition"), Следствие ("corollary") и т.д.

Наиболее прямолинейный подход - использовать Latex разметку, а именно - названия тэгов, и меры близости строк (название тэга - наименование концепта) для анализа. Древовидную модель исходного документа легко получить хотя бы на базе функциональности плагина Texlipse.  Правда, этот подход наталкивается на следующую трудность: в реальных документах названия тэгов часто сокращаются. Например, вместо
\begin{theorem}
...
\end{theorem}
можно увидеть конструкции с сокращенной (или измененной в общем случае) формой - thm, thms, thmnonum и т.д.
В этой связи естественно использовать алгоритмы близости строк, которые часто применяются в таких областях как интеграция данных, поиск дубликатов, биоинформатика и проч. Отобрал 7 наиболее распространенных:

1. Расстояние Левенштейна
2. Soundex
3. N-gram (c n=3)
4. Расстояние Jaro-Winkler
5. Расстояние Monge-Elkan
6. Алгоритм Needleman-Wunsch
7. Алгоритм Smith-Waterman

Природа алгоритмов довольно различна. Расстояние Левенштейна рассматривает количество операций вставки, удаления и замены, необходимых для совпадения строк; алгоритм Needleman-Wunsch приписывает операциям различную "стоимость"; алгоритм Smith-Waterman при этом использует соответствия стоимостей для всего алфавита;  Monge-Elkan различно оценивает стоимости операций согласно длинам несовпадающих подстрок ; Soundex использует звуковые коды символов; N-gram - количество общих n-грамм (чаще триграмм) или подпоследовательной длины n; Jaro-Winkler - количество общих символов при ослабленном ограничении на их позиции.
Реализацию этих и не только алгоритмов можно найти в библиотеке SimMetrics.

В результате анализа коллекции из 26 реальных научных публикаций получилась следующая интересная статистика. Основные показатели - точность и полнота в традиционном смысле.

1. Оптимальные значения мер по отношению к полноте

Levenshtein	0,29
SoundEx	0,77
N-gram	0,26
Jaro-Winkler	0,61
Monge-Elkan	0,34
Needleman-Wunsch	0,5
Smith-Waterman	0,29

Значения всех мер варьируются в диапазоне [0, 1]. При данных значениях получились следующие оценки точности и полноты.

2. Количество релевантных (R) и нерелевантных (N) пар, точность (Precision), полнота (Recall)

		R	N	Precision	Recall
Levenshtein		23	16	0,59	0,96
SoundEx		21	19	0,53	0,88
N-gram		23	4	0,85	0,96
Jaro-Winkler		23	16	0,59	0,96
Monge-Elkan		22	27	0,45	0,92
Needleman-Wunsch		14	38	0,27	0,58
Smith-Waterman		22	24	0,48	0,92

Выделены наиболее успешные алгоритмы. Безусловно, показатели N-gram алгоритма самые убедительные. Объясняется это, по всей видимости, следующими наблюдениями:

1. При именовании авторы склонны сохранять первые 2-3 символа в полном названии: lem - lemma; cor - corollary, assrt - assertion, defn - definition.
2. Из оставшейся части слова чаще выбрасываются гласные, чем согласные: proof - pf, thm - theorem.

Довольно очевидно, что первое наблюдение очень подходит для использования N-gram. В целом, точность на уровне 85% вполне приемлема для этого рода задачи.