Поиск по блогу

понедельник, 2 августа 2010 г.

Извлечение структурных элементов из 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
Levenshtein23 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% вполне приемлема для этого рода задачи.