СПОСОБ СОЗДАНИЯ И ИСПОЛЬЗОВАНИЯ РЕКУРСИВНОГО ИНДЕКСА ПОИСКОВЫХ МАШИН
METHOD OF GENERATING AND USING RECURSIVE INDEX OF SEARCH ENGINES

Настоящая заявка описывает способ построения и использования индекса поисковых машин и относится к области компьютерной техники и способам обработки информации.
Настоящее изобретение позволяет реализовать функциональность «вытягивания текста» из индекса поисковой машины с произвольного места в тексте, а также существенно снизить трудоемкость анализа совместной встречаемости слов в тексте, что, в свою очередь, позволяет делать предположения о неявных (причинно-следственных, ассоциативных и прочих) связях между объектами в их последовательностях. Изобретение расширяет возможность применения поисковых машин в области индексирования и поиска информации, представленной последовательностью объектов, отличных от объектов текстовой информации. Промышленная применимость изобретения показана на примерах создания и использования информации закодированной Хитами Индекса поисковой машины.
Краткое описание чертежей
Настоящее изобретение лишь проиллюстрировано как примерами, а не как ограничениями применения, сопутствующими чертежами в которых нумерация относится к сходным элементам, среди которых:
Фиг.1 - Кодирование Хитов поисковой машины Google, как это описано в работе «The Anatomy of a Large-Scale Hypertextual Web Search Engine» (1), Sergey Brin and Lawrence Page.
Фиг.2 - Базовый хит.
Фиг.3 - Расширение Базового Хита Google путем добавления полей «предыдущего» (Previous) и «последующего» (Next) слов и получение Расширенного Хита в соответствии с настоящим изобретением. Порядковые номера Предыдущего и Следующего слов указаны.
Фиг.4 - Расширенный Хит, в котором порядковые номера Предыдущего и Следующего слов не указаны. Их рассчитывают, зная значение position Базового Хита.
Фиг.5 - Пример текста для индексации.
Фиг.6 - Пример содержания Хитов рекурсивного Индекса проиндексированного текста, показанного на Фиг.5.
Фиг.7 - Расширенный Хит, в основе которого лежит структура данных Базового Хита Google.
Фиг.8 - Прямой (Forward) и обратный (Inverted) индексы Google из работы (1).
Фиг.9 - Расширенный Хит в соответствии с настоящим изобретением может описывать появление объекта любой природы в соответствующем массиве данных.
Фиг.10 - Добавление указателя «MetaID» доступа к метаданным, например указатель может указывать на местоположение маркировочной информации (tagging) формата ID3v2.
Фиг.11 - Пример таблицы совместной встречаемости нескольких слов языка.
Фиг.12 - Пример «вытягивания» из Рекурсивного Индекса предложений, проходящих через слово «TIGER».
Фиг.13 - Расширенная таблица Базового Хита, добавлен тип данных phrase.
Фиг.14 - Исходный вид сниппета, слово «удобный» выбрано курсором мыши.
Фиг.15 - Вид сниппета после того, как мышью «потянули» за слово «удобный». Это эффект «зуммирования» или «вытягивания» из индекса текста, центром которого является выбранное ранее слово «удобный».
Фиг.16 - Размещение в Расширенном Хите меток времени (TimeStamp) и меток местоположения (Location).
Фиг.17 - Расширенный Хит индекса с меткой времени TimeStamp.
Фиг.18 - Временной Рекурсивный Индекс.
Фиг.19 - Временной Рекурсивный Индекс с меткой местоположения Location.
Фиг.20 - Расширенный Хит Рекурсивного Путевого Индекса (местоположения Location).
Фиг.21 - Расширенный Хит Рекурсивного Путевого Индекса (метки времени TimeStamp).
Описание
Известны индексы поисковой машины Google и других поисковых машин, используемые для поиска информации в неструктурированных текстовых данных, размещенных в файловой системе, локальной сети или интернет, текстовых данных, содержащих разметку текста и включенные в текст объекты - графику, музыку, видео и прочее.
Прототипом Индекса поисковых машин является индекс слов бумажных книг, который известен издревле. Такой индекс слов располагается, как правило, в конце или начале бумажной книги и содержит список ключевых слов, которые содержатся в книге. Для каждого слова приводится перечень страниц книги, на которых это слово встречается. Аналогичным образом организован и индекс современных поисковых машин Интернет. В индексе содержится список (lexicon) всех известных слов языка, каждому из которых присвоен идентификатор wordID, список проиндексированных документов, каждому из которых присвоен идентификатор документа dociID, а каждое из появлений слова wordID в конкретном документе представлено Появлением или Хитом (hit). Хит является записью (Фиг.1), содержащей порядковый номер (position) искомого слова (wordID) в документе (docID).
Известен патент США №5265244, G06F 17/30 (20060101); G06F 012/00, описывающий способы построения индекса, но не описывающий содержание статистической информации, размещаемой в Хите индекса. Известен патент США №6490579 (G06F 17/30 (20060101); G06F 017/30) поиска информации с учетом контекстной информации, размещаемой в поисковом запросе. Известен патент США №7,925,641 (G06F 17/30 (20060101); G06F 7/00 (20060101)), описывающий способ индексирования web страниц и размещения в индексе поисковой машины атрибута URI и структуры контента сайта в дизайне, существующем на момент индексирования сайта.
http://infolab.stanford.edu/~backrub/gooqle.html)
Известна статья в работе «The Anatomy of a Large-Scale Hypertextual Web Search Engine», авторов Sergey Brin и Lawrence Page (далее именуется «работа (1)» , описывающая кодирование статистической информации Хитами индекса поисковой машины Google. Для обеспечения большей релевантности поиска в Интернете поисковые машины Интернет размещают в Индексе признаки, связанные с разметкой языка HTML и использованием гипертекстовых ссылок. Рисунок (Фиг.1), приведенный в работе (1), показывает, что Хит машины Google содержит порядковый номер position слова в нумерованном списке слов текста документа.
Кодирование хитов поясняется в разделе «4.2.5 Hit Lists» работы (1) так: «Существуют два типа хитов: сложные хиты (fancy) и простые хиты (plain). Сложные хиты относятся к URL, наименованиям, видимому тексту гиперссылки или к метаданным вэб страницы. Простые хиты относятся ко всему остальному. Простой хит состоит из бита заглавной буквы (сар:1), размера фонта (imp:3) и 12 битов позиции слова в документе (все позиции выше 4095 обозначены 4096). Размер фонта представлен относительно остальной части документа и использует три бита (на самом деле используются только 7 значений, поскольку значение 111 является флагом сложного хита). Сложный хит содержит бит заглавной буквы (сар:1), размер фонта равен 7 (imp:7), сигнализируя, что это сложный хит, 4 бита кодируют тип (type) сложного хита и 8 битов используются для позиции (position). Для якорного хита (anchor) 8 битов позиции разбиты на 4 бита для позиции в якорном тексте и 4 бита для хеша (hash) значения docID, в котором якорный хит был обнаружен. Это предоставляет ограниченную поисковую функциональность, ограниченную некоторым числом появлений конкретного слова в якорных текстах. Мы собираемся обновить способ размещения якорных хитов с тем, чтобы предоставить большее разрешение для полей позиции и хеша docID. Мы используем размер фонта относительно оставшейся части документа, так как, когда ищем, мы не хотим ранжировать во всем остальном одинаковые документы как разные только потому, что один документ использует больший размер фонта».
Как видно из приведенного описания работы (1), Хит поисковой машины Google кодирует информацию только об одном конкретном слове (wordID), расположенном в конкретной позиции (position) конкретного документа (docID), и далее мы станем называть такой хит «Базовым» (Фиг.2). Главной информацией, которую записывают в Базовый хит, является порядковый номер слова в индексируемом тексте (position), и мы продолжим называть ее номером слова (Position).
В общем, как было сказано выше, появление в тексте некоторого слова представлено в индексе Базовым Хитом, который зависит от набора переменных (cap, type, size, docID, wordID, position), таким образом Базовый Хит пожно условно представить функцией указанного набора переменных:
Базовый Хит = функция (cap, type, size, docID, wordID, position).
Настоящее изобретение предлагает Расширенных Хит, в котором в дополнение к информации Базового Хита размещается (Фиг.3), по меньшей мере, значение идентификатора (wordID) двух слов: «предыдущего слова», позиция которого в документе на единицу меньше и равна (position-1), и «следующего слова», позиция которого в документе на единицу больше и равна (position+1).
Несмотря на то, что в таблице Расширенного Хита (Фиг.3) мы указали позицию предыдущего<Previous Position>=<position-1>и последующего <Next Position>=<position+1> слов в записи Расширенного Хита, как было показано выше эти позиции можно вычислить, что позволяет позиции слов next и previous в записи Расширенного Хита не указывать и тем самым уменьшить объем данных Расширенного Хита индекса (Фиг.4).
Очевидно, что указатель документа DocID для всех трех слов остается по умолчанию одинаковым, так как все три слова являются последовательными словами текста одного и того же документа, имеющего идентификатор DocID.
Таким образом, в соответствии с настоящим изобретением появление некоторого слова в тексте было бы описано Расширенным Хитом как функцией набора переменных так:
Расширенный Хит = функция (cap, type, size, docID, wordID, position, Previous WordID, Next WordID)
или
Расширенный Хит = функция (Базовый Хит, Previous WordID, Next WordID).
Переход от Базового Хита индекса современных поисковых машин к Расширенному Хиту индексу в соответствии с настоящим изобретением позволяет сохранять исходных текст в индексе и восстанавливать исходных текст из индекса, а также повысить эффективность проведения анализа совместной встречаемости слов текста с использованием индекса, по сравнению с тем, как это было возможно, используя Базовый Хит индекса ранее.
В качестве иллюстрации для текста, показанного на Фиг.5, содержание Расширенных хитов Рекурсивного индекса с использованием Расширенных Хитов показано на Фиг.6.
Рекурсивное вытягивание текста из Индекса
Для примера рассмотрим случай Расширенного Хита, в основе которого лежит Базовый Хит поисковой машины Google, а индекс построен для текстовой информации (Фиг.7).
Настоящее изобретение впервые позволяет реализовать рекурсивное «вытягивание» текста из индекса, начиная с любого стартового хита StartHit. Для краткости станем обозначать Previous WordID (предыдущее слово) как <WordID-1> и Next WordID (последующее слово) как <WordID+1>, имея в виду, что номер Предыдущего слова в тексте равен <position-1> и номер Следующего слова в тексте равен <position+1>. Тогда StartHit (Хит текущего слова, находящегося между предыдущим <WordID-1> и следующим <WordID+1> словами) будет представлен следующей зависимостью:
StartHit = Расширенный Хит (WordID, docID, position, WordID-1, WordID+1).
Далее опишем операцию «Восстановления» исходного текста из индекса, представленного Расширенными Хитами. «Восстановление» исходного текста представлено следующими шагами:
Шаг 1:
Извлекаем из StartHit указатели <WordID-1> и/или <WordID+1>.
Шаг 2:
В списке Lexicon (Фиг.8) ищем входы <WordID+1> и/или <WordID-1> и переходя в Обратный Индекс (Inverted Barrels) находим Расширенные Хиты: следующий (NextHit) и предыдущий (PrevHit) соответственно для <WordID+1> и <WordID-1> с номерами слов текста (position+1) и (position-1) для того же документа docID, которые можно записать так:
NextHit = Расширенный Хит (<WordID+1>, docID, position+1, WordID, <WordID+2>)
или
PrevHit = Расширенный Хит (<WordID-1>, docID, position-1, <WordID-2>, <WordID>))
Шаг 3:
Повторяем Шаг 1 и Шаг 2 для записей PrevHit и/или NextHit, извлекая <WordID-3> и <WordID-+3>, переходим к записям Расширенных Хитов для <WordID-3> и <WordID-+3> и так далее до некоторого номера N и соответственно <WordID-N> и <WordID-+N> или до некоторого стоп слова StopWordID.
В результате N повторений Шагов 1 и 2 «Восстановления» получим цепочку слов <WordID-N>→…→<WordID--3>→<WordID--2>→<WordID--1>→<WordID>→<WordID-+1>→<WordID-+2>→<WordID-+3>→…→<WordID-+N>. Текст можно восстанавливать или до начала, или до конца текста, а можно выбрать некоторое условие останова «вытягивания» исходного текста, обозначенное некоторым «стоп словом» (StopWord). В случае использования стоп слова получим цепочку <StorWord>→…→<WordlD--3>→<WordID--2>→<WordID--1>→<WordID>→<WordID-+1>→<WordID-+2>→<WordID-+3>→…→<StorWord>. Стоп словом может служить, например, знак «точка», разделяющая предложения, или номер N в выражении <position+-N>, или другое условие останова «вытягивания» исходного текста из индекса. В случае, например, когда условием останова является конец предложения, «Восстановление» будет происходить, пока не будут достигнуты начало и/или конец предложения. Стоп словом также может служить, например, слово, начинающееся с заглавной буквы (флаг Заглавной буквы <cap>), расположенное в якорном тексте, или слово, имеющее другой признак останова. Точно также можно восстанавливать не одно предложение, а произвольное число предложений текста. Условием остановки «Восстановления» может служить любое условие, которое можно сформулировать для поисковой машины.
Наличие в Индексе признаков «заглавной буквы» (cap) и других атрибутов форматирования текста позволяет восстанавливать текст с той или иной степенью соответствия оригиналу. Расширение числа признаков до числа признаков форматирования, используемых в текстовых редакторах, позволило бы восстанавливать тексты без отличий от исходного оригинала, который был проиндексирован.
Важной особенностью изобретения является то, что оно позволяет индексировать не только текст, но также массивы информации любой природы, представленные нумерованной значением <position> последовательностью объектов.
Для объектов отличной от текста природы цепочка восстановленных объектов будет выглядеть соответственно так:
<Предыдущий Объект N> →…→ <Предыдущий Объект 2> → <Предыдущий Объект 1> → <Предыдущий Объект> → <Объект> → <Следующий Объект 1> → <Следующий Объект 2> →…→ <Следующий Объект N>
или со стоп объектом так:
<Стоп Объект> →…→ <Предыдущий Объект 2> → <Предыдущий Объект 1> → <Предыдущий Объект> → <Объект> → <Следующий Объект 1> → <Следующий Объект 2> →…→ <Стоп Объект>.
Наличие в Расширенных Хитах индекса Предыдущего и Следующего Объектов, позволяет индексу обращаться к самому себе, для извлечения очередного i-го PreviousObject или i-го NextObject, имеющих соответственно номера <position-i> и <position+i> в нумерованной последовательности Объектов исходного массива информации.
Имея в виду свойство рекурсивного «восстановления» последовательности объектов из изобретенного индекса, далее мы станем называть изобретенный индекс Рекурсивным Индексом.
Возможность частичного или полного восстановления текста исходного документа или массива данных другой природы путем его «вытягивания» из Рекурсивного Индекса делает возможным множество полезных применений настоящего изобретения в быту и технике. Ниже приведены некоторые из таких применений.
Индексирование объектов разной природы
Поскольку в современном Интернете помимо текстов присутствует геодезическая информация, медиа информация и множество других типов данных, число которых постоянно увеличивается, то настоящее изобретение предлагает использовать не идентификаторы слов (wordID), а идентификатор объекта любой природы, а библиотеки могут состоять не только из текстовых документов, но также из видеоматериалов, картинок, звуковых файлов, файлов координатной информации и любых других файлов. В этой связи в число идентификаторов, от которых зависит Хит, помимо docID и WordID может быть например тип библиотеки libraryID, вместо docID можно использовать идентификатор источника sourceID, а вместо идентификатора слов WordID можно использовать идентификатор объекта object ID и так далее. Рисунок (Фиг.9) показывает кодирования Расширенного Хита объектов любой природы (включая текст), где Базовый Хит кодирует текущий объект, NextID является идентификатором объекта, следующего в цепочке за текущим, и PrevID является идентификатором объекта, предшествующего текущему объекту в цепочке (Фиг.9).
Метаданные Рекурсивного Индекса
http://atomicparsley.sourceforqe.net/mpeq-4files.html
В настоящее время известно много форматов, в том числе медиа форматов, требующих размещения богатой мета информации. В частности это относится к ID3 tag для файлов МР3 и к Metadata файлов MPEG4 (). к данным бегущей текстовой строки для караоке, формату TimedText для фильмов с субтитрами и так далее.
Для расширения функциональности Рекурсивного индекса с целью поддержки индексирования медиа данных и других видов данных, настоящее изобретение предлагает размещение указателя «MetaID» в информации Расширенного Хита (Фиг.10). Метаданные, которые описывает MetaID, расширяют формат Базового Хита, дополняя описание объекта, позицию которого содержит Базовый Хит. Поскольку файлы метаданных MPEG, MP3, MPEG4, караоке и биометрических данных и так далее могут отличаться друг от друга, то MetaID, например, может содержать указатели места размещения метаданных.
Расширенный Хит поисковой машины может иметь множество применений, примерами которых могут служить: размещение списка запросов к поисковой машине, ранжированных по рейтингу в качестве метаданных Рекурсивного Временного Индекса рейтинга поисковых запросов; размещение в Рекурсивном Временном Индексе рецепта приготовления пищи, в котором метаданными могут служить описания ингредиентов, их весовые или объемные доли, температурный режим, описание используемой посуды и другие особенности процесса приготовления; размещение в Индексе последовательности шагов проведения химической реакции или размещение последовательности картографических точек дорог или маршрутов движения и так далее…
Анализ совместной встречаемости объектов
Путем анализа совместной встречаемости слов языка можно установить, какие из словосочетаний являются устойчивыми, а какие нет. Некоторые из устойчивых словосочетаний могут оказаться понятиями, для которых нет одного слова. Таким понятием, например, может служить словосочетание «Нейро-лингвистическое программирование». Очевидно, что встречаемость слов в последовательности <нейро → лингвистическое → программирование> будет существенно выше, чем слов обратной последовательности <программирование → лингвистическое → нейро>. В приведенном примере словосочетание <нейро → лингвистическое → программирование> образует понятие «НЛП». Выявление различного веса прямой и обратной сочетаемости («анизотропия» сочетаемости) слов позволяет делать предположения об устойчивом сочетании слов или позволяет сделать предположение о существовании неявных связей между словами и понятиями, включая причинно-следственные или ассоциативные связи. Так Таблица совместной встречаемости (Фиг.11) содержит условный вес совместной встречаемости слов рассмотренного словосочетания «нейро-лингвистическое программирование» (Фиг.11).
Предположим (Фиг.11), словосочетания «нейро-лингвистическое» и «лингвистическое программирование» встречаются с одинаковой частотой 0,7. Вместе с тем двумерная таблица не позволяет установить вес совместной встречаемости словосочетания трех слов «нейро-лингвистическое программирование», для решения последней задачи пришлось бы строить трехмерную матрицу 3*3*3 слов.
Таким образом, решение задачи совместной встречаемости каждых двух слов из N слов языка, потребует создания двумерной таблицы N*N слов языка и занесения в нее рейтингов совместной встречаемости каждых двух слов, на пересечении которых находится ячейка рейтинга совместной встречаемости. А для изучения совместной встречаемости трех слов понадобилось бы построить уже куб размером N*N*N и так далее, что усложняет задачу экспоненциально.
G
Поскольку современные поисковые машины используют Базовый Хит, содержащий позицию одного слова, то поиск сочетаний слов, а также анализ частоты взаимной встречаемости двух и более слов языка можно решать только путем построения таблицы N, где G представляет собой число слов в одном сочетании. Как было показано выше, решение задачи таким способом связано с высокой трудоемкостью и экспоненциальным ростом трудоемкости при увеличении числа слов в словосочетании. Этим объясняется то, что Google и другие поисковые машины не позволяют эффективно искать фразы, содержащие более трех слов.
G
Использование Рекурсивного Индекса позволяет существенно снизить трудоемкость решения задачи анализа совместной встречаемости сочетаний G слов из N слов языка, перейдя от анализа многомерной области N слов языка к анализу ограниченной области с радиусом R слов языка, где R>=G, как это показано ниже.
Решение задачи совместной встречаемости с использованием рекурсивного индекса
Для изучения совместной встречаемости, например, слова «лингвистическое» мы «вытягиваем» из Рекурсивного Индекса все цепочки слов, в которых встречается слово «лингвистическое», ограничиваясь некоторым числом R слов до и после слова «лингвистическое». Здесь число R служит условием останова «вытягивания» исходного текста из рекурсивного индекса. Таким образом, если через слово «лингвистическое» проходит множество предложений одного документа или множество предложений разных документов, то в качестве результата «вытягивания» мы получаем сферу из слов с радиусом R слов, в центре которой находится слово «лингвистическое». Если условием останова «вытягивания» будет знак «точка», то мы сможем вытягивать слова до и после слова «лингвистическое» до знака «точка», означающего конец и начало предложения, в котором встретилось слово «лингвистическое». Пример такой сферы, ограниченной началом и концом предложения, центром которой является слово Tiger, показан на Фиг.12. В случае использования конца или начала предложения в качестве условия останова, радиусом Сферы будет не R слов, а одно или R предложений, центральное предложение сферы, при этом будет содержать слово, за которое мы «тянули».
Далее мы можем проводить анализ совместной встречаемости слова «лингвистическое» с другими словами в объеме «вытянутых» цепочек текста. Понятно, что все словосочетания «нейро-лингвистическое программирование» попадут в поле нашего зрения, так как все они попадают в Сферу радиуса R=одно слово или R=одно предложение. Понятно также, что анализ всех предложений, включающих такое словосочетания в указанном радиусе, не представляют большой трудоемкости даже для настольного компьютера. Таким образом, Рекурсивный Индекс и его архитектура, построенная на использовании Расширенного Хита, позволяют решить задачу поиска и анализа совместной встречаемости слов с существенно большей эффективностью, чем это позволяет делать индекс современных поисковых машин, включая Google и другие поисковые машины.
Проиллюстрируем вышесказанное еще на одном примере.
Фиг.12 показывает цепочки слов, проходящие через слово «TIGER» «вытянутые» из Рекурсивного Индекса с R=одно предложение. Все приведенные предложения являются частью одного документа, но относятся к разным Хитам слова Tiger в этом документе, однако Рекурсивный Индекс, содержащий Хиты из разных документов, позволяет проводить анализ с такой же эффективностью по всему множеству доступных документов. Как видно, в цепочках повторно встречаются различные формы слова «large», а также слова «big», «cat», из чего можно сделать вывод о возможной связи слова «tiger» со словами «big», «cat» и «large». Причем слова «big» и «cat» встречаются два раза вместе, что может указывать на существование устойчивого словосочетания «big→cat». Устойчивость произвольного словосочетания Word1→Word2 можно проверить, «вытянув» из Рекурсивного Индекса все цепочки слов, центром которых в одном из случаев будет, например, слово Word1 (слово за которое «тянули», в приведенной на Фиг.12 примере было слово «Tiger»). Для того чтобы проверить тоже самое словосочетание Word1→Word2 на совместную встречаемость в обратном направлении Word1→Word2, следует «потянуть» за слово Word2 из индекса цепочки слов и анализировать в вытянутых цепочках слов, случаи, когда NextWord для Word2 является Word1. Если, например, частота встречаемости сочетания Word1→Word2 окажется существенно больше частоты встречаемости сочетания Word2→Word1, то это будет указывать на то, что сочетание Word1→Word2 является устойчивым, а сочетание Word2→Word1 случайным. Так, например, вытягивая цепочки слова «big» или Хит-слова «cat» и проводя анализ совместной встречаемости слов «big» и «cat», в вытянутых цепочках можно установить, является ли словосочетание «big cat» устойчивым или случайным. На примере Фиг.12 видно, что сочетание «big cat» встречается чаще, чем «cat big», из чего можно сделать вывод о возможной устойчивости словосочетания «big cat» и вероятном отсутствии словосочетания «cat big».
Совместную встречаемость слов (или других объектов) можно понимать и шире, чем образование словосочетаний (сочетаний объектов).
Такие слова, как «огонь» и «дым», могут не образовывать словосочетания, но имеют причинно-следственную связь, из-за которой их появление в одном тексте имеет более высокую вероятность, чем слов, не имеющих причинно-следственной связи. Это обстоятельство позволяет ожидать, что на большой статистике текстов такая вероятность даст всплеск совместной встречаемости слов, не образующих устойчивые словосочетания, но связанных причинно-следственными связями. Можно также ожидать, что встречаемость слов может иметь преимущественное направление, например встречаемость «огонь→дым» может оказаться выше, чем обратная встречаемость «дым→огонь», что может указывать на причинно-следственную связь между словами или понятиями. Можно также ожидать, что, исследуя словосочетания, состоящие из трех слов и более, анализ совместной встречаемости позволит выявлять устойчивые словосочетания PreviousWord(i)→NextWord(j), что позволит делать заключения о наличии связи между словами PreviousWord(i)→NextWord(j). Можно предполагать, что если помимо сочетаемости Предыдущего слова с Текущим (PreviousWord(i)→CurrentWord) и Текущего слова со Следующим (CurrentWord→NextWord(j)) существует прямая сочетаемость слов Предыдущее слово→Следующее слово (PreviousWord(i)→NextWord(j)), то такая связь является ассоциативной, поскольку такая связь обусловлена Текущим словом, но напрямую с ним не связана, а значит Текущее слово играет роль ассоциативной связи между Предыдущим словом и Следующим словом. Различие частоты прямой PreviousWord(i)→NextWord(j) и обратной сочетаемости NextWord(j)→PreviousWord(i) позволит сделать предположение о причинно-следственной связи в ассоциативной цепочке слов или других объектов.
Индексирование выявленных понятий
Поскольку Базовый Хит современных поисковых машин описывает позицию одного слова, а не понятия, то в случаях, когда такое слово является частью устойчивого словосочетания, Базовый Хит не обеспечивает релевантности индексации и поиска информации, так как отдельные слова устойчивого словосочетания не имеют отдельного смысла и являются носителем смысла только когда используются совместно! Часто понятия обозначаются аббревиатурами, таким образом, для них появляется отдельное «слово» языка.
Аналогичная ситуация сложилась со словосочетаниями, составляющими название торговой марки или рекламного слогана, названия песни или фильма, на которые распространяются авторские права их обладателей. Такие словосочетания также становятся устойчивыми для идентификации продукции, фильма, песни или другого предмета авторских прав. Автоматическое выявление таких устойчивых словосочетаний также является трудоемким при использовании индекса Google и других поисковых машин.
Как было показано выше, Рекурсивный Индекс позволяет эффективно проводить анализ совместной встречаемости слов и выявлять устойчивые словосочетания, представляющие понятие, слоган или наименование. Для выявленных устойчивых наименований Рекурсивный Индекс содержит, как было сказано выше, Google использует значение imp=7 в качестве флага для индикации сложного хита. Фиг.13 показывает один из возможных способов расширения функциональности Базового Хита путем кодирования устойчивых словосочетаний, обозначенных «phrase», флагом для обозначения хита устойчивого словосочетания в качестве примера принято нулевое значение размера фонта imp=0, type:2 кодирует число слов в словосочетании (до 4 слов) и 8 битов значения position относится к первому слову словосочетания.
Вместе с тем понятно, что кодирование Базового Хита (Фиг.2, 13) не отражает сегодняшних реалий Интернета как с точки зрения объема информации (даже 12 битов значения position может оказаться недостаточно для кодирования позиции объекта), так и с точки зрения типов данных (plain, phrase, fancy, anchor), поэтому приведенное кодирование расширенной таблицы Базового Хита является лишь иллюстрацией описанного настоящим изобретением способа расширения функциональности индекса поисковых машин.
Индексирование выявленных неявных связей
Для индексирования объектов, имеющих неявную связь с Базовым Хитом, настоящее изобретение предлагает использовать поле метаданных MetaID, куда заносится указатель на файл объектов, ассоциативно/причинно-следственно связанный с Хитом в контексте конкретного документа. Таким образом, для каждого отдельного Хита одного и того же WordID найденного в разных документах docID содержание MetaID будет уникальным и отвечающим контексту использования WordID конкретного Базового Хита.
Некоторые практические применения Рекурсивного Индекса
Рекурсивный Индекс текстов
Рекурсивный индекс, в частности, позволяет упростить Интерфейс пользователя (User Interface или UI) поисковой машины и улучшить «usability» поиска, позволив пользователю «вытягивать» курсором цепочки слов из Сниппета (snippet) в списке результатов поиска, потянув за любое слово, расположенное в тексте сниппета. «Вытянутый» таким образом текст позволяет пользователю с минимальными усилиями понять, насколько результат поиска, представленный таким сниппетом, релевантен поисковому запросу пользователя, не прибегая с загрузке web страницы, сниппет которой был показан в результатах поиска. «Зуммирование» текста сниппетов в результатах поискового запроса к поисковой машине показано на рисунках ниже (Фиг.14, 15). Под «Зуммированием» в данном случае мы имеем в виду «вытягивание» курсором выбранного в тексте сниппета слово (в данном случае слово «удобный»). «Зуммирование» приводит к «вытягиванию» из Рекурсивного Индекса слов текста слева и справа от выбранного слова и вывод «зуммированного» текста в окно просмотра.
Рекурсивный Индекс времени и местоположения
Базовый Хит не является чувствительным к местоположению и времени, так как учитывает лишь положение слова в тексте (Фиг.2). В то же время для видео и аудио хроники (живого общения, речи и событий записанных на видео) время и место может иметь существенное значение. Для индексации объектов, чувствительных ко времени и местоположению, наряду с номером появления <position> следует использовать метки времени <TimeStamp> и координаты <Location>, например геодезические (Фиг.16).
В такой индекс можно записывать, например, распознанные объекты, появляющиеся в кадре при съемке видеокамерой, закрепленной, например, на движущемся автомобиле.
Размещение метки времени TimeStamp или метки сдвига по времени TimeOffset относительно некоторого известного времени TimeStamp (например, относительно времени начала записи звука или видео) в Хитах слов для результатов распознавания речи, при «вытягивании» текста из Рекурсивного Индекса позволяет передать темп произнесения слов во времени. В такой реализации значениями WordID, NextID и PrevID могут являться слова говорящего, коды распознанных видео образов или цифровые объекты другого происхождения, появление которых связано хронологически.
Рекурсивный Индекс для индексации картины мира
Известно, что картина мира для человека складывается из информации, попадающей в мозг через каналы чувств (зрение, осязание, слух, обоняние, вкус, термоцепция и другие). Фиксация поступающей в каждый канал чувств человека информации имеет хронометрический характер и потому может быть представлена Рекурсивным Индексом ощущений. Для зрения - это объекты, которые попадают в поле зрения, а для уха - это ряд звуков, которые улавливаются ухом, и так далее. Таким образом, текст, являющийся результатом распознавания речи, может использовать Расширенные Хиты временного рекурсивного индекса слов (Фиг.17), содержащий также ссылки на предыдущее и следующее слово <Next WordID> и <Prev WordID>.
Если учесть, что события реальной жизни связаны также с местоположением, то наличие в Расширенном Хите не только метки времени TimeStamp, но и метки местоположения Location (Фиг.16) может оказаться важным. Метка местоположения может носить более общий характер и содержать геодезические или некие относительные координаты, например смещение местоположения LocationOffset относительно некоторого известного местоположения Location (например от местоположения начала маршрута), а также идентификатор источника данных, как, например, наименование телеканала. Расширенный Хит (Фиг.16) показан не для Слова, а для любого другого Объекта, видеообраза, химического вещества, местоположения и так далее.
В настоящее время в различных лабораториях проводятся работы по идентификации и синтезу запахов, а также по идентификации и воспроизведению других ощущений человека, и можно представить, что через некоторое время медиа файлы будут содержать не только изображение, звук и строку субтитров, но также информацию о запахе, вкусе, тактильных ощущениях и прочее. Размещение таких данных в соответствующих Рекурсивных Индексах позволит осуществлять по ним поиск, «вытягивать» временные цепочки таких данных для использования, а также проводить анализ их взаимной встречаемости. Метки времени, размещенные в Рекурсивном Индексе, позволят синхронизировать воспроизведение данных из разных Рекурсивных индексов, содержащих информацию разных каналов чувственного восприятия, а метки местоположения позволят делать геодезическую или другую привязку местоположения.
Временной Рекурсивный Индекс
Временной Рекурсивный Индекс содержит вместо WordID метки времени TimeStamp (Фиг.18). Идентификатор MetaID указывает на место размещения метаданных, относящихся к описываемому моменту времени TimeStamp, а метки времени Prev TimeStamp и Next TimeStamp указывают соответственно на Предыдущую метку времени и на Следующую метку времени. В Хите метки времени возможно размещение метки местоположения Location (Фиг.19) или другой необходимой информации.
Рекурсивный Путевой Индекс
Поскольку свойством Рекурсивного Индекса является запоминание последовательности следования объектов индексации, то становится возможным рекурсивное индексирование последовательностей геодезических координат и адресов, представляющих, например, маршруты движения или картографическую информацию дорожной сети. При этом адреса или геодезические координаты точек маршрута вносятся в индекс вместо WordID (Фиг.20 и 21).
Аппаратная реализация работы с Рекурсивным Индексом
Создание поисковой системы, в которой файл Рекурсивного Индекса отделен от Программы анализа и поиска Рекурсивного Индекса (ПАПРИ), позволяет реализовать ПАПРИ в аппаратном виде и ускорить работу ПАПРИ, а также сделать чип, предназначенный для встраивания в различные устройства, связанные с обработкой информации. Последнее обстоятельство позволяет создать устройства, способные «на лету» индексировать распознанные видеообразы, речь, поток данных, поступающих через каналы связи, и любые данные, мгновенно предоставляя возможность поиска в таких данных.
Распределенный Рекурсивный Индекс
Рекурсивная Индексация web сайта или данных персонального или сетевого компьютера/сайта/файла с последующим размещением полученного файла Рекурсивного Индекса на проиндексированном сайте/компьютере/файле позволяет создать модель распределенного Рекурсивного Индекса файловой системы/компьютера/локальной сети или Интернет, при котором Рекурсивные Индексы каждого компьютера или сайта находятся на самом компьютере/сайте, что позволяет предоставить пользователям локальный Рекурсивный поиск по компьютеру/сайту/файлу, без необходимости обращаться к поисковой машине сети или Интернет. Аппаратная реализация ПАПРИ позволяет организовать работу с локальными файлами Рекурсивного Индекса, не обращаясь к центральной поисковой машине. Ниже приведены некоторые примеры автономного размещения рекурсивного индекса. Возможность построения распределенного Рекурсивного Индекса позволяет создать поисковую машину Интернет с распределенным Рекурсивным Индексом.
Повышение релевантности работы поисковой машины
Использование анализа совместной встречаемости в рекурсивном индексе позволяет повысить релевантность поиска поисковых машин, в том числе поисковых машин Интернет.
Для этого дополнительно к поисковому запросу, содержащему одно или несколько слов, в поисковую машину может быть введен образцовый текст с использования слов запроса. Такой текст далее индексируется, и из него создается рекурсивный индекс.
Устанавливается некоторая теоретическая или эмпирическая Избранная Мера Совпадения результатов анализа совместной встречаемости появления одного и того же слова в разных массивах данных.
Для слов поискового запроса производится анализ совместной встречаемости слов запроса со словами образцового текста. Далее производится поиск в индексе поисковой машины Хитов появления слов поискового запроса, а для найденных Хитов производится анализ совместной встречаемости слов поискового запроса с другими словами массивов данных, проиндексированных поисковой машиной, а также анализа совместной встречаемости с другими словами поискового запроса.
Полученные результаты анализа совместной встречаемости слов поискового запроса в образцовом тексте (Образцовые результаты) сравниваются с результатами анализа совместной встречаемости слов поискового запроса в массивах данных, проиндексированных поисковой машиной (Результаты машины), и если мера совпадения Образцовых результатов с Результатами машины соответствует Избранной Мере Совпадения, то найденный Хит считается релевантным результатом поиска.
Некоторые примеры применений Рекурсивного Индекса
Одним из важных применений может служить индексирование видеоинформации - фильмов, видеорепортажей, результатов видеонаблюдения, фотографий и так далее. Индексировать видеоматериалы можно как с помощью Рекурсивного Текстового Индекса, так и с помощью Рекурсивного Временного Индекса. Так, создавая Рекурсивный Индекс текстовой информации субтитров, распознанной речи или текста (Speech or text recognition) с метаданными, служат распознанные видеообразы - лица людей или объекты (face/object recognition). Наоборот, для Рекурсивного Временного Индекса видеоматериала метаданными может служить видеокадр, распознанное изображение и текст. Создание Рекурсивного Индекса видеоматериалов позволит создать механизм поиска распознанных изображений и текста сопровождающего видео, а также позволит создать машину индексирования видеорепортажей и видеоматериалов в реальном времени, что, в свою очередь, позволит встретить такую технологию индексации и поиска видеоданных в фотоаппараты, видеокамеры, телефоны и другие носимые устройства, способные создавать видео, а также компьютеры и другие устройства, способные проигрывать ранее созданное видео.
Пример 1. Размещение рекурсивного индекса данных в медиа файлах
Технология размещения бегущей строки текста песни в «Караоке» или текста субтитров в видеофильмах реализуется с помощью технологии Timed Text или аналогичной технологии, описанной соответственными индустриальными или корпоративными стандартами производителей оборудования и носителей медиа данных.
Применение технологий распознавания лиц и объектов (face и object recognition), распознавание текста (text recognition), а также распознавание речи (speech recognition) позволяет преобразовывать видеоданные и звуковые данные видеозаписей (включая фильмы) и потокового видео в уникальные цифровые коды лиц, объектов и текст оптически распознанного текста и речи. Поскольку распознанные лица, объекты и текст, а также текст распознанной речи представляют собой временную последовательность объектов, представленных в видеоматериалах в машиночитаемом цифровом виде, то после распознавания речи и видеообразов становится возможной их индексация рекурсивным индексом и позволяет предложить хронометрический поиск по распознанным объектам для видеоматериалов, а также хронометрический поиск и позиционирование по тексту речи и поиск появившихся в видеоматериале объектов и лиц.
Индексирование в соответствии с настоящим изобретением распознанных объектов видеосъемки впервые предоставляет возможность поиска распознанных объектов и «вытягивание» событий, предшествующих появлению распознанного объекта или последующих за появлением распознанного объекта. В свою очередь, это позволяет многократно снизить трудоемкость поиска объектом поиска в материалах видеонаблюдения.
Телефон в настоящее время позволяет просто разговаривать, а также осуществлять видеозвонки. Индексирование в соответствии с настоящим изобретением распознанной речи и лиц позволяет создать технологию автоматического стенографирования телефонных переговоров, с возможностью поиска распознанного текста и видеообъектов в их хронологической последовательности.
http://atomicparsley.sourceforqe.net/mpeq-4files.html
http://www.id3.org/ID3v2Easv
Для медиа файлов форматов MP3, а также MPEG4 отраслевыми стандартами предусмотрено размещение маркировочной информации в маркировочной системе ID3 (tagging system) и других маркировочных системах (). В частности, система ID3v2  способна содержать до 256 мегабайт информации любого содержания, содержащей метаданные медиа файла MP3 или MPEG4. Это позволяет размещать в метаданных ID3v2 полные Рекурсивные Индексы текста субтитров фильма на всех языках, рекурсивные индексы песен, книг, а также рекурсивный индекс распознанных видео образов, распознанный текст и текст распознанной речи.
Индексирование текста электронной книги в соответствии с настоящим изобретением позволяет «вытягивать» текст книги из рекурсивного индекса, начиная с любого слова текста, что позволяет использовать рекурсивный индекс в качестве источника текста электронной книги.
Размещенный в маркировочной системе (ID3 или другой) Рекурсивный Индекс предоставляет возможность поиска текстовой и видеоинформации в метаданных для медиа файлов, включая, но не ограничиваясь аудио форматами CD, MP3, WMA, AAC, AIFF, M4A и видео форматами DVD, Blu-Ray, HD, MP4, AVI, MOV, RAM, SWF, WMV и другими известными медиа форматами, а также возможность «вытягивания» части или полного текста, и/или образов видеоряда произведения в их хронометрическом порядке, осуществления в нем поиска, проведение анализа данных, взаимной встречаемости данных с помощью техники, описанной в настоящей заявке. Размещение Рекурсивного Индекса в метаданных ID3 медиа файлов и в метаданных любого другого формата позволяет реализовать функции «вытягивания» данных, поиска в них, анализа данных на предмет совместной встречаемости и выявление возможных ассоциативных и причинно-следственных связей, независимо от используемого формата, создает основу для индексации и поиска данных любого происхождения и содержания.
Пример 2. Тексты электронных книг
http://en.wikipedia.org/wiki/Comparison_of_e-book_formats
Известно множество открытых и корпоративных форматов электронных книг e-books . Вместе с тем использование Рекурсивного Индекса для публикации электронных книг позволяет «вытягивать» текст книги непосредственно из Рекурсивного индекса и одновременно предоставить пользователю функцию поиска в тексте и анализа текста с помощью Рекурсивного Индекса.
Пример 3. Рекурсивный индекс картографической информации.
Размещая в файле Рекурсивного индекса геодезические координаты точки, можно индексировать маршруты движения или схему дорог с учетом разрешенного направления движения.
Пример 4. Рекурсивный Индекс новостей и RSS лент
Новости поступают в разное время, маркеры которого могут использоваться вместо слов для индексирования в Рекурсивном Временном Индексе, Рекурсивный Текстовый Индекс.
Бизнес модели
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в электронных книгах.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в аудиокнигах.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в электронных источниках картографической информации, в том числе геодезической.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в устройствах навигации.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в устройствах связи.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в компьютерах, в том числе мобильных.
Взимание оплаты за создание и/или размещение, и/или использование Рекурсивного Индекса в телефонах, смартфонах, навифонах и медиа устройствах таких как iPod и другие.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса с носителей видео информации, таких как CD, DVD, Blu-Ray и любых других форматов, уже известных, и тех, которые будут использоваться в будущем, включая, но не ограничиваясь аудио форматами MP3, WMA, AAC, AIFF, M4A и видео форматами MP4, AVI, MOV, RAM, SWF, WMV.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса web сайта или ссылки на такой Рекурсивный Индекс web сайта в метаданных web сайта или в структуре данных Semantic Web названного сайта.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса в структуре данных Semantic Web.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса поисковой машины в локальной сети.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса поисковой машины в сети Интернет.
Взимание оплаты за создание и/или запись, и/или считывание Рекурсивного Индекса поисковой машины в произвольной сети коммуникаций.
Взимание оплаты за создание и/или размещение, и/или показ рекламы контекстно или по другому связанной с данными, извлеченными из Рекурсивного Индекса.
Взимание оплаты за проектирование и/или создание, и/или распространение, и/или использование программного обеспечения, способного создавать Расширенные Хиты рекурсивного Индекса, содержащие информацию о Следующем Объекте или Предыдущем Объекте.
Взимание оплаты за проектирование и/или создание, и/или распространение, и/или использование программного обеспечения, способного извлекать из Расширенных Хитов Рекурсивного Индекса информацию о Следующем Объекте или Предыдущем Объекте.
Взимание оплаты за проектирование и/или создание, и/или распространение, и/или использование программного обеспечения, способного создавать Расширенные Хиты Рекурсивного Индекса, содержащие Предыдущий или Следующий Объекты распознавания, распознанные программой распознавания речи (speech recognition), распознавания текста (optical character recognition или text recognition), распознавания лица (face recognition) или распознавания любого другого зрительного объекта или объекта другой природы (химического, геодезического и так далее).
Взимание оплаты за проектирование и/или создание, и/или распространение, и/или использование аппаратного обеспечения (чипа, контроллера, процессора и так далее), способного создавать Расширенные Хиты рекурсивного Индекса, содержащие информацию о Следующем Объекте или Предыдущем Объекте, извлекать из Расширенных Хитов Рекурсивного Индекса информацию о Следующем Объекте или Предыдущем Объекте, проводить анализ совместной встречаемости Объектов.