Local File Search Engine
1.0.0
Это базовая реализация системы поиска файлов на основе Python для ответа на запросы в текстовых файлах в локальной системе. Мы использовали «взвешивание терминов tf-idf» и «косинусное сходство» для ранжирования релевантности совпадающих документов. Вычисления tf-idf выполняются заранее, что значительно ускоряет поиск. Также для ускорения поиска был использован Стемминг (Porter Stemmer). Предоставляется базовый пользовательский интерфейс с использованием библиотеки Python Tkinter.
python2 createIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat
createIndex_tfidf.py запустится только один раз для расчета значений tdf-idf по всему корпусу.
python2 queryIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat
Всего на этом этапе создаются три разных файла:
titleIndex.dat
В этом файле хранится уникальный docId (идентификатор документа), который присваивается каждому документу в корпусе.
testIndex.dat
При этом создается индексный файл (также известный как структура данных инвертированного индекса), который содержит информацию обо всех уникальных терминах (кроме стоп-слов), встречающихся во всех документах. Каждому документу присваивается уникальный идентификатор, начиная с 0, который хранится в titleIndex. дат. Информация о термине хранится в индексном файле следующим образом: term|docID0:pos1,pos2;docID1:pos3,pos4,pos5;…..|tf0,tf1,tf2...|idf Здесь tf0,tf1,tf2 представляет частоту терминов в docID0, docID1, docID2 соответственно. idf представляет обратную частоту документа, а pos1 представляет положение термина в соответствующем документе и так далее.
линии.dat
В этом файле хранится информация о строках, в которых присутствует термин в различных документах. Эта информация о строке представлена как: term|docID0:line1,line2;docID1:line3,line4,line5.
Перед созданием этих файлов все термины документов проверяются в списке стоп-слов. Если термин появляется в стоп-словах, то он пропускается, иначе его информация сохраняется в этих файлах. Кроме того, каждый термин перед добавлением в индекс проверяется Портером Стеммером.
При этом, прежде всего, вся информация из файловlines.dat, titleIndex.dat и testIndex.dat снова сохраняется с использованием словаря Python.
Теперь поддерживаются следующие типы запросов:
Запросы из одного слова (OWQ) Это запрос с одним термином, и его выходные данные представляют собой список документов, содержащих запрошенный термин, а также номера строк, в которых этот термин присутствует в соответствующем документе.
Запросы из нескольких слов (MWQ). Входные данные в MWQ представляют собой последовательность слов, а выходные данные — список документов, которые содержат любые термины запроса вместе с номерами строк.
Фразовые запросы (PQ) Входные данные в PQ снова представляют собой последовательность слов, а соответствующие документы — это те, которые содержат все термины запроса в указанном порядке.
Теперь, когда мы нашли список документов, в которых присутствует запрос, пришло время их ранжировать. Схема ранжирования, которую мы здесь использовали, основана на tf-idf. Tf-Idf — это схема взвешивания, которая присваивает каждому термину в документе вес на основе его частоты термина (tf) и обратной частоты документа (idf). Термины с более высокими весовыми показателями считаются более важными. Это одна из самых популярных схем взвешивания в информационном поиске.
Частота термина (tf) зависит от документа. По сути, это количество вхождений термина t в документе D. Вполне логично выбрать tf в качестве параметра, поскольку чем больше термин появляется в документе, тем он становится более важным. Мы можем представить документ вектором, размер которого равен номеру. уникальных терминов в документе, и каждое значение обозначает количество терминов в данном документе. Представление документов в виде векторов в общем векторном пространстве известно как модель векторного пространства и имеет фундаментальное значение для поиска информации. Но здесь есть один недостаток. По мере увеличения размера документа вес tf будет увеличиваться по мере увеличения частоты терминов. Таким образом, документ, содержащий ту же информацию, что и другой документ, скопированный более одного раза, будет считаться более важным. Чтобы устранить этот недостаток, мы разделим каждое значение вектора на его норму, чтобы вектор стал единичным вектором.
Мы не можем использовать частоту терминов только для расчета веса термина в документе, поскольку tf считает все термины одинаково важными. Однако некоторые термины встречаются реже и являются более дискриминационными, чем другие. Если мы используем tf исключительно в качестве меры для ранжирования, то если мы будем искать по такой теме, как звуковые волны, мы можем в конечном итоге получить много документов, содержащих световые волны и другие волны, поскольку частота термина является единственным параметром.
Чтобы смягчить этот эффект, мы используем обратную частоту документов. Частота появления термина в документе — это, по сути, количество документов, содержащих этот термин. Таким образом, обратная частота документов (idf) термина — это количество документов в корпусе, разделенное на частоту документов термина. Обычно было обнаружено, что коэффициент idf довольно велик, и лучшие результаты получаются, если мы используем log(idf). Поскольку log является возрастающей функцией, мы можем использовать ее, не ухудшая наши результаты.
Мы определили и tf, и idf, и теперь можем объединить их, чтобы получить окончательную оценку термина t в документе d. Мы снова представим документ в виде вектора, где каждая запись представляет собой вес tf-idf соответствующего термина в документе. Вес tf-idf термина t в документе d — это просто умножение его tf на его idf.
Теперь мы построили векторы каждого документа на основе веса tf-idf. Пришло время ответить на запрос, используя заданные векторы документов. Прежде всего, мы создадим сам вектор запроса на той же основе, что и вектор документа, то есть на основе оценки tf-idf (учитывая запрос самого документа). Теперь, когда у нас готов вектор запроса, мы найдем все те документы, в которых присутствует наш запрос. Теперь мы возьмем скалярное произведение вектора запроса и вектора документа, в котором присутствует запрос. Чем выше скалярное произведение, тем больше сходства вектор запроса с вектором документа , что означает, что угол между вектором документа и вектором запроса невелик. Этот метод поиска сходства между запросом и документом называется косинусным сходством.
