WikiDer > Индексация срока

В Информатика, а указатель срока это структура данных для облегчения быстрого поиска терминов и статьи в логическая программа,^[1] дедуктивная база данных, или же автоматическое доказательство теорем.

Обзор

Многие операции в автоматических средствах доказательства теорем требуют поиска в огромных наборах терминов и предложений. Такие операции обычно выполняются по следующей схеме. Учитывая коллекцию ${ displaystyle S}$ терминов (предложений) и условия запроса (предложение) ${ displaystyle q}$, найти в ${ displaystyle S}$ некоторые / все термины ${ displaystyle t}$ относится к ${ displaystyle q}$ в соответствии с определенным условием поиска. Наиболее интересные условия поиска сформулированы как наличие подстановки, которая особым образом связывает запрос и извлекаемые объекты. ${ displaystyle t}$. Вот список условий поиска, часто используемых в пруверах:

• срок ${ displaystyle q}$ унифицировано с термином ${ displaystyle t}$, т.е. существует подстановка ${ displaystyle theta}$, так что ${ Displaystyle д тета}$ = ${ Displaystyle т тета}$
• срок ${ displaystyle t}$ это пример ${ displaystyle q}$, т.е. существует подстановка ${ displaystyle theta}$, так что ${ Displaystyle д тета}$ = ${ displaystyle t}$
• срок ${ displaystyle t}$ является обобщением ${ displaystyle q}$, т.е. существует подстановка ${ displaystyle theta}$, так что ${ displaystyle q}$ = ${ Displaystyle т тета}$
• пункт ${ displaystyle q}$ включает статью ${ displaystyle t}$, т.е. существует подстановка ${ displaystyle theta}$, так что ${ Displaystyle д тета}$ является подмножеством / подмножеством ${ displaystyle t}$
• пункт ${ displaystyle q}$ входит в ${ displaystyle t}$, т.е. существует подстановка ${ displaystyle theta}$, так что ${ Displaystyle т тета}$ является подмножеством / подмножеством ${ displaystyle q}$

Чаще всего мы действительно заинтересованы в явном поиске подходящих замен вместе с извлеченными терминами. ${ displaystyle t}$, а не просто в установлении существования таких замен.

Очень часто размеры наборов терминов, подлежащих поиску, велики, запросы на поиск часты, а условия поиска довольно сложны. В таких ситуациях линейный поиск в ${ displaystyle S}$, когда условие поиска проверяется на каждом термине из ${ displaystyle S}$, становится непомерно дорогим. Чтобы преодолеть эту проблему, специальные структуры данных, называемые индексы, разработаны для поддержки быстрого поиска. Такие структуры данных вместе с соответствующими алгоритмами обслуживания и поиска индексов называются методы индексации терминов.

Классические техники индексирования

• деревья дискриминации
• деревья замещения
• индексирование пути

Деревья подстановки превосходят индексирование путей, дерево различения и деревья абстракции.^[2]

Индекс терминов дерева дискриминации хранит свою информацию в три структура данных.^[3]

Современные методы индексирования

• индексирование векторов признаков
• кодовые деревья
• деревья контекста
• реляционная индексация пути

Рекомендации

дальнейшее чтение

• П. Граф, Term Indexing, Lecture Notes in Computer Science 1053, 1996 (немного устаревший обзор)
• Р. Секар, И.В. Рамакришнан и А. Воронков, Term Indexing, в A. Робинсон и А. Воронков, редакторы, Справочник по автоматическому мышлению, том 2, 2001 г. (недавний обзор)
• W. W. McCune, Эксперименты с индексированием дерева дискриминации и индексированием пути для поиска терминов, Journal of Automated Reasoning, 9 (2), 1992
• П. Граф, Индексирование дерева подстановки, Proc. of RTA, Lecture Notes in Computer Science 914, 1995
• М. Стикель, Метод индексации путем индексации терминов, Tech. Реп. 473, Центр Искусственного Интеллекта, SRI International, 1989
• С. Шульц, Простое и эффективное включение предложения с индексированием вектора признаков, Proc. семинара IJCAR-2004 ESFOR, 2004 г.
• Рязанов А., Воронков А. Частично адаптивные кодовые деревья // Тр. JELIA, Конспект лекций по искусственному интеллекту 1919, 2000
• Х. Ганзингер, Р. Ньювенхейс и П. Нивела, Быстрое индексирование с использованием кодированных контекстных деревьев, Журнал автоматизированного рассуждения, 32 (2), 2004 г.
• А. Рязанов и А. Воронков, Эффективное извлечение экземпляров с помощью стандартной и реляционной индексации путей, информации и вычислений, 199 (1-2), 2005 г.