Способ, система и компьютерный программный продукт для поиска, навигации и ранжирования документов в персональной сети

Способ, система и компьютерный программный продукт для поиска, навигации и ранжирования документов в персональной сети

Иллюстрации

Показать все

Реферат

Ссылки на связанные заявки

Настоящая заявка содержит предмет, связанный с заявкой на патент США 10/687602, поданной 29 октября 2003 г., и с заявкой на патент США 10/918713, поданной 25 августа 2004 г., полное содержание которых включено сюда посредством ссылки. Настоящая заявка также заявляет приоритет по предварительной заявке 60/610221, поданной 16 сентября 2004 г., полное содержание которой включено сюда посредством ссылки.

Область техники, к которой относится изобретение

Способ, устройство и компьютерный программный продукт для помощи в поиске и навигации среди файлов. Способ обеспечивает построение сети ссылок, соединяющих документы, и пригоден по меньшей мере в случае, когда такая сеть не существует предварительно, например для отдельного пользователя или маленькой группы, совместно использующей документы.

Уровень техники

Текущее состояние удручает любого пользователя персонального компьютера. Пользователь приучен находить в Сети по существу немедленно почти все, что его интересует, по любой теме, выбирая из сетевых документов, число которых сейчас превышает 8 миллиардов, причем результаты ранжированы так хорошо, что обычно несколько совпадений при поиске с наивысшим рангом дают пользователю то, что он просил. Кроме того, для пользователя несложно, найдя хорошее совпадение, следовать по связям от этого совпадения и таким образом обнаруживать связанные документы.

В то же время у того же пользователя есть, возможно, тысячи или миллионы файлов на его персональном компьютере. Этому пользователю нужно также осуществлять поиск и навигацию по этим файлам. Причина этого, конечно, в том, что число файлов делает невозможным запомнить, что это за файлы, где они находятся в иерархической файловой системе и что они содержат. Таким образом, пользователю нужна помощь: а) в поиске конкретных файлов и б) в поиске файлов, относящихся к теме. Это, конечно, в точности тот тип помощи, который можно получить - в случае Сети - от существующих поисковых машин Сети. Удрученный пользователь может спросить, почему настолько труднее найти что-то в его собственном компьютере?

Настоящее изобретение предназначено для удовлетворения как раз этой потребности. То есть это изобретение предлагает способы для поиска и навигации среди персональных файлов. Оно также подходит для поддержки тех же функций для файлов, совместно используемых группами (пользователей).

Текущее состояние технологии поддержки поиска и навигации по персональным файлам достаточно ограниченно. Как отмечено выше, в настоящее время имеется отчетливый разрыв между потребностями пользователя в поиске по растущим объемам персонального содержимого и способностью современной технологии удовлетворить эту потребность. В последнее время многие различные компании осознали этот разрыв и усиленно работают над его заполнением, так как большая неудовлетворенная потребность представляет большую возможность для предпринимательства. Следовательно, при обсуждении текущего состояния техники мы будем включать в него как ограниченные технологические решения, которые можно купить и использовать сегодня, так и такие, относительно которых были сделаны объявления или намеки в средствах массовой информации. Особенность состоит в том, что эта область находится в состоянии быстрого роста и изменения.

Идея «поиска на рабочем столе» - означающая поисковое приспособление для локального запуска на собственном компьютере пользователя - уже существует некоторое время. Одна из первых поисковых машин Интернета, AltaVista, в 1998 году начала «дарить» свободное программное обеспечение для персональных компьютеров под названием AltaVista Discovery. Здесь мы видим раннее осознание факта, который сейчас понимают многие: абсолютное число цифровых документов, к которым должен иметь отношение даже один пользователь, возросло настолько, что старый иерархический метод организации и навигации по файлам стал безнадежно неадекватным.

Microsoft осознала проблему, перед которой стоят пользователи ПК, ищущие информацию в компьютерных файлах, более десяти лет назад. Microsoft'овское видение унифицированного хранилища данных в ее операционной системе Windows (Cairo, включающей в себя OFS - объектную файловую систему (Object File System); идеи, восходящие по меньшей мере к 1990 г.) явилось источником многих публичных сообщений. Эти сообщения продолжаются до настоящего времени и часто пересматриваются. (После нескольких отсрочек текущая объявленная дата запуска для следующей версии Windows под кодовым именем Longhorn - это 2006 г.) Решение, предлагаемое Microsoft, состоит в замене базового доступа в ее операционной системе Windows технологией, заимствованной из ее программного обеспечения баз данных SQL Server. В настоящее время документы, сетевые страницы, файлы электронной почты, электронные таблицы и другая информация запоминаются в раздельных, большей частью несовместимых программах. Новая технология под кодовым именем WinFS обещает унифицировать хранение в единой базе данных, встроенной в Windows, которая будет допускать более легкий поиск, будет более надежна и доступна из корпоративных сетей и Интернета.

В октябре 2004 г. Google выпустила бета-версию своей машины Google Desktop Search. В противоположность «все капитально ремонтирующему» подходу Microsoft Google Desktop Search состоит из относительно малого и легко загружаемого набора программных модулей, которые сканируют и индексируют содержимое пользовательского компьютера. Индекс затем используется для поддержки быстрого поиска. Индексируемые документы включают в себя текстовые файлы, файлы Word, Powerpoint, Excel, почтовые файлы Outlook и просмотренные сетевые документы.

Впоследствии (в декабре 2004 г.) Microsoft выпустила бета-версию ее Microsoft Toolbar Suite, охватывающую как поиск на рабочем столе, так и поиск в Сети. Перед этим Microsoft приобрела технологию поиска на рабочем столе Lookout; Lookout, как очевидно из ее названия, ориентирована на поиск в файлах Outlook.

Также в декабре 2004 г. Ask Jeeves представила бета-версию загружаемой машины поиска на рабочем столе. Эта машина, вероятно, включает в себя технологию, полученную от компании Tukaroo, которую купила Ask Jeeves. В том же месяце Yahoo объявила, что она выпустит тест-версию в начале 2005 г. Yahoo закупила большое количество ранее разработанных технологий, из которых наиболее заметна Overture, которая сама закупила некоторые (поисковые) машины, в том числе AllTheWeb. Yahoo разрабатывает свою машину поиска на рабочем столе совместно с X1.

Есть много других компаний, предлагающих продукты для поиска на рабочем столе. Краткое резюме выше, без сомнения, быстро устаревает; поэтому мы не стремимся к полноте. Обзор компаний и продуктов для поиска на рабочем столе может быть найден в http://www.goebelgroup.com/desktopmatrix.htm.

Важный вопрос состоит в том, какую технологию используют эти новые игроки. Некоторая информация может быть обнаружена в общедоступных объявлениях этих компаний; но очень трудно найти какие-либо детали о действительной технологии поиска, которая используется. Кажется ясным, что громадное большинство этих фирм предлагает поиск, основанный на ключевых словах, с использованием индексации по различным типам файлов; многие также предлагают поиск как по рабочему столу, так и по предприятию. Однако мы не нашли ни одной компании, которая явным образом основывает ранжирование результатов поиска на анализе связей. На самом деле неясно, использует ли какая-либо из этих компаний связи вообще - либо для ранжирования, либо для навигации.

Технология, очевидно использующая связи, - это технология Autonomy Corporation. Autonomy недавно запустила IDOL Enterprise Desktop Search. Технология Autonomy включает симметричные «связи подобия» между документами. Мера подобия сложна и использует вероятностные измерения подобия понятий. В процессе поиска также используется анализ понятий вместо опоры исключительно на ключевые слова. Однако нет признаков использования односторонних гиперсвязей, таких как использованные в настоящем изобретении, и нет свидетельств использования анализа связей. Фактически Autonomy явным образом отказалась от использования любого вида техники ранжирования страниц. То есть, как отмечено в пресс-релизе, доступном на http://www.autonomy.com/content/Press/Archives/2004/1206.html: «Вместо ранжирования страниц, подхода, доказавшего свою неэффективность в области, свободной от связей, Руководство Автоматического Запроса использует кластеризацию понятий».

Таким образом, как обнаружено авторами настоящего изобретения, для построения хороших средств поиска, ранжирования и навигации для широкого множества видов документов предпочтительно иметь соответствующую структуру связей в локальной файловой системе, которая может быть использована в анализе связей. Вид структуры связей, присутствующий во Всемирной Паутине, представляет людям много лучший способ связываться с информацией, чем традиционная иерархическая файловая система, в которой каждый документ втиснут в единственное место иерархического дерева. Если такая структура связей уже присутствует на сегодняшних компьютерах, то, возможно, уже существует и основанное на анализе связей устройство поиска и ранжирования для локальных жестких дисков.

Ни одно из решений, предложенных к настоящему времени, не строит необходимую инфраструктуру связей для обеспечения основанного на анализе связей ранжирования для поиска и навигации по файлам для отдельного пользователя или небольшой группы. Настоящее изобретение исправляет это положение, предлагая способ генерации локальной структуры связей.

Как детально объясняется ниже, гиперсвязи (гиперссылки) могут обеспечивать два типа информации: они могут показывать подобие между двумя файлами (симметрично) и (или) предполагать рекомендацию, что пользователь, начинающий с файла A, может посчитать файл B интересным (односторонне или асимметрично). Кроме того, связи могут быть использованы для двух целей: они могут помочь в поиске (через ранжирование) и в навигации.

Существующие технологии для систем документов не из Всемирной паутины либо совсем не имеют гиперсвязей - таким образом упуская преимущества как ранжирования, так и навигации - или используют только подобие (как Autonomy). В последнем случае теряется возможность использования человеческих суждений для обеспечения рекомендаций о файлах и об отношениях между файлами. Без таких рекомендаций и поиск (ранжирование), и навигация теряют в качестве.

Анализ связей (ссылок) сыграл решающую роль в огромном успехе машины поиска в Сети Google. До Google основные подходы к ранжированию совпадений при поиске использовали одно или несколько из: релевантности текста, «популярности связи» и человеческого суждения (Yahoo). Релевантность текста важна всегда, но сама по себе недостаточна для получения хороших результатов ранжирования. Популярность связи характеризуется подсчетом связей, указывающих на страницу. Популярность связи - это самая грубая форма анализа связей, и ее слишком легко исказить фальшивыми связями. Наконец, человеческое суждение, хотя и всегда полезно, слишком медленно и дорого для распределенных систем документов с большим количеством документов и высокой скоростью оборота.

Google была первой, известной авторам изобретения, поисковой машиной в Сети, использующей нетривиальный анализ связей при помощи хорошо известного алгоритма PageRank (ранжирования страниц). Преимущество PageRank - вместе с другими формами нетривиального анализа связей, такими как указано в заявке на патент США 10/687602 и заявке на патент США 10/918613, - состоит в том, что PageRank использует коллективную форму человеческого суждения. Это значит, что большая часть громадного числа связей, соединяющих миллиарды сетевых страниц, проложена миллионами людей (разработчиками сетевых страниц). Следовательно, нетривиальный анализ связей является разумным способом использовать бесплатную работу этих миллионов людей, извлекая их коллективное суждение, чтобы найти лучшие сетевые страницы.

Большей частью, когда разработчик сетевой страницы устанавливает связь со своей собственной страницы A на другую страницу B, это значит (по мнению разработчика сетевой страницы), что читатель, заинтересовавшийся страницей A, возможно, также заинтересуется страницей B. То есть такая связь может интерпретироваться как влекущая некоторую смесь двух факторов: (i) что страница B подобна странице A и (или) (ii) что страница B, возможно, интересна кому-либо, заинтересовавшемуся страницей A.

Коротко: анализ связей ценен потому, что связи выражают две вещи: подобие и рекомендацию.

Хотя эти подходы и применялись в сетевых окружениях, потребители оказались перед дилеммой, как работать с тысячами или миллионами файлов, расположенных на их персональных компьютерах.

Авторы настоящего изобретения осознали желательность инструментов разработки Персональной Сети связей, позволяющей пользователю ранжировать совпадение при поиске по ключевому слову и обеспечивающей навигацию по этим файлам. Термин «Персональная Сеть» относится к сети связей между документами, построенных при помощи настоящего изобретения. Персональная Сеть включает в себя комбинацию из: (i) ненаправленных взвешенных связей, основанных на подобии; (ii) направленных взвешенных связей, которые могут или не могут быть привязанными к тексту в указывающем или указанном документе и которые представляют рекомендацию, и (iii) весов (оценок важности), приписанных документам самим по себе - опять-таки представляющим рекомендацию.

Ранжирование и навигация всегда будут важными функциями в мире больших информационных массивов. Персональная сеть поддерживает обе эти функции единственным и эффективным способом - включением в себя двух решающих аспектов подобия и рекомендаций - как детально обсуждается далее.

Сначала мы рассмотрим подобие. Настоящее изобретение использует машинные алгоритмы для вычисления подобия между документами или файлами. Как отмечено выше, по меньшей мере один из других подходов (подход Autonomy) использует анализ подобия между документами для поддержки пользователя при поиске и навигации по этим документам. Данная мера подобия отличается от меры, принятой Autonomy. Другое отличие состоит в использовании взвешенных связей подобия, которые генерируются ранее описанным анализом подобия как компонентом общего подхода к анализу связей, который, в свою очередь, поддерживает ранжирование совпадений при поиске. Кроме того, связи подобия играют важную роль в поддержке навигации.

Затем мы переходим к рекомендации. Рекомендации часто лучше всего выполняются людьми. Однако в случае единственного пользователя оценка его собственных файлов несколько отличается от случая оценки файлов в Сети. В Сети миллионы пользователей сотрудничают в рекомендациях относительно миллиардов сетевых страниц. В этой ситуации каждый пользователь дает рекомендации для относительно малого числа других документов. В случае одного пользователя для него часто оказывается невозможным или непрактичным проходить через множество ранее существовавших файлов и пытаться установить связи, указывающие на другие связанные или интересные файлы. Иными словами, невозможно просто создать «Сеть на рабочем столе», пытаясь создать персональную Сеть так же, как Всемирную паутину, так как бремя работы для одного пользователя слишком велико.

Другое отличие от Всемирной паутины также существенно. Это отличие состоит в том, что единственный пользователь часто оказывается единственным человеком, который может оценить степень интереса к его собственным файлам - никто другой не может сделать этого, и машина также не может. Пользователь должен прочитать или, по меньшей мере, хотя бы немного знать все эти файлы. В противоположность этому во Всемирной паутине не существует способа, которым один человек мог бы оценить все страницы Сети.

Подводя итог этим двум различиям: в Сети многие люди выполняют работу чтения и многие люди выполняют работу рекомендации/оценивания через гиперсвязи. В случае единственного пользователя можно ожидать, что один человек (хотя и не безупречно) выполняет работу чтения файлов; и, кроме того, нельзя ожидать, что этот же человек захочет выполнять работу установления связей от каждого файла к другим. Это несоответствие между ресурсами лиц, дающих рекомендации, и числом документов, которые должны быть просмотрены/рекомендованы, препятствует какому-либо систематическому применению гиперсвязей к системам документов, отличных от Всемирной паутины.

Для учета этого несоответствия настоящее изобретение включает в себя гибридную форму рекомендации. Эта гибридная форма обеспечивает пользователю возможность установки гиперсвязи от одного файла к другому. Эта гибридная форма обеспечивает также другой механизм рекомендации: каждому файлу дается «оценка качества файла» (ОКФ) (FQS). У каждого файла есть значение по умолчанию, которое находится достаточно низко на шкале возможных FQS. Это значение может быть изменено автоматически на основании таких измерений, как новизна и/или частота использования документа. Кроме того, пользователь может увеличить (или уменьшить) эту FQS по желанию, когда это удобно - например, после открытия/чтения файла. FQS является наименее трудоемким способом включения рекомендаций в систему документов. Настоящее изобретение добавляет даже еще бóльшую гибкость за счет обеспечения дополнительной возможности выбранных пользователем гиперсвязей. Именно в этом смысле один вариант осуществления системы рекомендаций является гибридным: он включает в себя как веса вершин в графе (документы с их FQS), так и направленные связи между вершинами (тем самым рекомендуя указанный документ из указывающего документа).

Сущность изобретения

Способ, устройство и компьютерный программный продукт для персональной поисковой машины, включающей в себя Персональную Сеть, состоящую из: сети подобия, гиперсвязей (генерируемых вручную и автоматически) и оценок качества файлов, обновляемых как вручную, так и автоматически. Компоненты включают в себя синтаксический анализатор (выделяющий слова из документов); анализатор релевантности текстов; способ анализа связей; сеть подобия; анализатор подобия и гиперсвязи, применяемые к персональным файлам на компьютере. Другие компоненты включают в себя навигационное окно и FQS. Комбинация всего вышеперечисленного может быть включена в работающую машину персонального поиска.

Краткое описание чертежей

Фиг.1 иллюстрирует два типа гиперсвязей между документами, используемых в настоящем изобретении.

Фиг.2 представляет собой блок-схему алгоритма поисковой машины согласно одному варианту осуществления настоящего изобретения.

Фиг.3 является представлением гибридной Сети согласно одному варианту осуществления изобретения.

Фиг.4 представляет собой блок-схему алгоритма навигации согласно одному варианту осуществления изобретения.

Фиг.5 является иллюстрацией структуры единственной группы с точки зрения единственного пользователя согласно одному варианту осуществления изобретения.

Фиг.6 является иллюстрацией согласно одному варианту осуществления изобретения двух возможных путей определения поднабора файлов, используемых для построения подграфа и выполнения анализа связей, для случая нескольких групп.

Фиг.7 является иллюстрацией согласно одному варианту осуществления изобретения двух возможных подграфов, используемых для анализа связей, для случая нескольких групп.

Фиг.8 представляет собой блок-схему компьютера, используемого в одном варианте осуществления изобретения.

Подробное описание изобретения

Настоящее изобретение включает в себя построение «Персональной Сети» среди документов, которые иначе имели бы ограниченную структуру связей или не имели бы никакой. Персональная Сеть включает в себя комбинацию из: (i) ненаправленных взвешенных связей на основе подобия; (ii) направленных взвешенных связей, которые могут или не могут быть привязанными к тексту в указывающем или указанном документе и которые представляют рекомендацию, и (iii) весов (оценок важности), приписанных документам самим по себе - опять-таки представляющих рекомендацию.

Для описания этой структуры мы используем также термин «гибридная Сеть». Персональная Сеть является гибридной в двух смыслах. Во-первых, она использует гибридную смесь взвешенных симметричных связей подобия и взвешенных направленных связей рекомендации. Во-вторых, важная функция рекомендации достигается с помощью гибридной смеси направленных связей и оценок качества файлов (FQS).

Далее мы тщательно разрабатываем гибридную форму рекомендации, используемую в настоящем изобретении. Этот гибридный подход обеспечивает пользователю возможность прокладки гиперсвязи от любого файла к любому иному файлу. (Как видно ниже, эта гиперсвязь может или не может быть привязана к конкретному тексту с любого конца.) В этом контексте мы предлагаем точное определение термина «гиперсвязь», чтобы избежать неопределенности. Логически гиперсвязь представляет собой указатель, который указывает из файла (скажем, файла А) на другой файл (скажем, файл В). Помимо того, можно связать с этим указателем вес гиперсвязи (HLW). Это логическое определение (указатель плюс вес) подразумевается, когда бы мы ни использовали термин гиперсвязь в описании настоящего изобретения. Физически такие гиперсвязи воплощаются, как правило, в виде метаданных, которые обычно включаются в метаданные файла А (хранятся с ними) - указывающий файл. Кроме того, любой вес, связанный с гиперсвязями, также хранится как метаданные - обычно (опять-таки) для файла А.

В дополнение к гиперсвязям подход гибридных рекомендаций обеспечивает другой механизм рекомендации: каждому файлу будет придана оценка качества файла, или FQS. Первоначально каждому файлу для его FQS дается значение по умолчанию, которое достаточно низко по шкале возможных FQS. Пользователь может затем увеличить (или даже уменьшить) эту FQS по желанию.

Кроме того, в одном варианте осуществления изобретения могут использоваться автоматические способы изменения FQS. Например, компьютер может сам зарегистрировать число раз, когда файл открывается и (или) редактируется за период времени, и дать более высокие оценки FQS файлам, которые открываются часто. Кроме того, недавность обращения может быть использована как мера важности.

Обоснование для этой гибридной системы состоит в следующем. Во-первых, не требуется никакого истощающего труда. Рекомендации получают только файлы, для которых пользователь побуждается сделать это. Во-вторых, выбор FQS легче, чем установка связей, - это, по всей видимости, наименее требовательная форма возможной рекомендации. И еще здесь необходимы минимальные усилия пользователя. Файлы начинаются с FQS по умолчанию; ее, в свою очередь, можно видоизменить определенными измеряемыми машиной указателями (индикаторами) важности. Только те файлы, которые пользователь сочтет «раздражающими», получат видоизмененное пользователем (как правило, увеличенное) значение FQS.

Отсюда проявляется следующая картина. Пользователь без сомнения начнет свое первое использование «поисковой машины персональной Сети» с большого задела файлов. Машина сама затем примется бороздить систему пользовательских файлов, сканировать тексты файлов, строить инвертированный индекс и строить «сеть подобия», которая помещает взвешенные симметричные связи между каждой парой файлов. Вес связи является мерой подобия. Кроме того, машина назначает низкую FQS по умолчанию каждому файлу, возможно, видоизменяя это значение по умолчанию на основе информации из файловых журналов.

Следовательно, пользователь вообще без каких-либо усилий получает сеть подобия, соединяющую все файлы, оценку важности для каждого файла и инвертированный индекс. Эти признаки уже позволяют проводить поиск и навигацию. Пользователь может затем дополнить эту начальную картину установкой рекомендаций. Мотивацией для этого является то, что они представляют собой «напоминания самому себе». Если пользователь прокладывает гиперсвязь от файла А к файлу В, то это напоминание, которое говорит: «Когда я открыл А, я, вероятно, захочу перейти к В». Далее, используемые здесь гиперсвязи, как и гиперсвязи в Сети, можно встраивать в текст так, чтобы они указывали на конкретные места в тексте в файле А и (или) на конкретные места в файле В.

Читатель/владелец файла может также проложить рекомендации (самому или самой себе) с помощью FQS. Например, если читатель взамен выбирает увеличение FQS файла С от его заданного значения, то это напоминание вида «Я хочу, чтобы файл С имел шанс подняться выше среднего, когда я провожу поиск файлов». Аналогично читатель может пожелать понизить FQS файла, который он счел малоинтересным, даже хотя его и не надо удалять.

Получающаяся гибридная сеть будет иметь как симметричные (ненаправленные) связи, так и односторонние или направленные связи. Математически такой граф является все же направленным графом, а потому его можно обрабатывать подходящими для направленных графов способами (такими как описанные в ранее присоединенной заявке на патент США №10/687602, поданной 29 октября 2003 г., и в заявке на патент США №10/918713, поданной 25 августа 2004 г.).

Сюда вовлекается настроечный параметр при определении того, сколько веса должна иметь направленная записанная пользователем гиперсвязь по сравнению с весами подобия на симметричных связях подобия. То есть один вариант осуществления настоящего изобретения использует анализ связей для ранжирования документов; и входом в анализ связей является гибридная Сеть, составленная как из ненаправленных связей подобия, так и из направленных гиперсвязей. Относительные веса этих двух типов связей будут, таким образом, влиять на результаты анализа связей. В предпочтительном варианте осуществления изобретения веса подобия будут попадать в диапазон от 0 до 1. Далее, в одном варианте осуществления изобретения гиперсвязям придается вес по умолчанию, равный 1. Альтернативно (поддерживая веса подобия в том же самом диапазоне от 0 до 1) гиперсвязям может быть придан вес по умолчанию, но настраиваемый (т.е. регулируемый пользователем) HLW.

FQS дают для каждого документа еще и третью оценку, которую можно использовать в дополнение к оценкам из анализа связей и анализа релевантности текстов. То есть ранжирование совпадений поиска основывается на комбинации: (i) оценки релевантности текста, (ii) веса анализа связей и (iii) FQS. Опять-таки здесь имеется два настроечных параметра для использования при определении относительной значимости, которую надо придать этим трем весам.

Наконец, мы переходим к навигации. Настоящий вариант осуществления включает в себя три механизма помощи в навигации.

Во-первых, имеются те гиперсвязи, которые присоединены к тексту. Присоединенные гиперсвязи работают для пользователя аналогично использованию гиперсвязей для навигации по Всемирной паутине: текст в документе выделяется, тем самым сообщая пользователю, что этот текст соединен с гиперсвязью на другой документ (или на другое место в этом же документе). Во-вторых, вариант осуществления позволяет пользователю устанавливать неприсоединенные гиперсвязи, которые указывают из файла А на файл В. В-третьих, сеть подобия обеспечивает связи к каждому иному файлу из файла А.

Отметим здесь, что термин «гиперсвязь» обычно используется для ссылки на тот выделенный текст, который используется для представления пользователю (на интерфейсе) присоединенной гиперсвязи. В данном документе термин «гиперсвязь» относится к логическому указателю (с весом), как обсуждалось выше. Следовательно, мы будем использовать термин «активная иконка» для любого выделенного текста (или иного символа), который представляется пользователю на интерфейсе, чтобы пользователь мог активировать эту иконку и тем самым открыть указываемый файл. То есть иконка на интерфейсе не является гиперсвязью по нашему определению; скорее, гиперсвязью является логический (взвешенный) указатель «позади» иконки.

Как показано на фиг.1, гиперсвязь присоединяется к тексту в указывающем документе 3 и указывает на указываемый документ 4. Неприсоединенная гиперсвязь 2 указывает из указывающего документа 3 на указываемый документ 4. Возможно также иметь гиперсвязь, присоединенную к конкретному тексту в указываемом документе. К примеру, на фиг.1 присоединенная гиперсвязь 5 указывает из текста «текст 1» в указывающем документе 3 на текст «важный» в указываемом документе 4.

Для поддержки навигации настоящее изобретение позволяет пользователю, который открыл файл О, остановить навигационное окно, показывающее файлы, с которыми связан О. Это окно будет иметь три ранжированных списка. Один список будет заполняться связями подобия высшего ранга. Эти связи будут ранжироваться весом подобия, оценкой анализа связей и FQS связанного файла. Второй список будет иметь файлы высшего ранга, на которые указывают гиперссылки из О, - ранжированные согласно их значениям FQS, их оценкам АС (LA) анализа связей и их весам гиперсвязи. Третий список будет затем иметь файлы высшего ранга, которые указывают на О, - опять-таки ранжированные своими FQS, своими оценками АС и весами гиперсвязи.

Теперь перейдем более детально к компонентам описанного выше изобретения со ссылкой на фиг.2, которая описывает как процесс поиска, так и настоящее изобретение в виде поисковой машины и ее компонентов.

Пользователь инициирует поиск 225 ведением ключевых слов 223 в поисковый интерфейс. Ключевые слова подаются в генератор 235 списка совпадений. Генератор списка совпадений использует ключевые слова для получения списка 237 совпадений из инвертированного индекса 233.

Инвертированный индекс представляет собой файл, который берет одно ключевое слово в качестве входных данных, а затем выдает список файлов, содержащих это ключевое слово, в качестве выходных данных. Это стандартная технология, она использует методы, которые общеизвестны специалистам. Для многоключевых поисков нужна также способность извлекать из инвертированного индекса все файлы, удовлетворяющие некоторой булевой комбинации ключевых слов. Здесь снова можно использовать известные методы. Этот вид сортирующей по булевым выражениям функции включается в компонент, называемый «инвертированный индекс».

Чтобы построить инвертированный индекс, нужен синтаксический анализатор (221 на фиг.2). Этот компонент сканирует файлы 201 и распознает слова в этих файлах. Многие типы файлов в настоящее время позволяют использовать синтаксические анализаторы, например файлы программы Word, файлы с расширением pdf, текстовые файлы, файлы в формате html, файлы почты Outlook. Действие синтаксического анализатора и построение и обновление инвертированного индекса имеют место в фоновом процессе, который не инициируется поиском.

Отметим здесь, что персональные файлы обычно имеют большое число нетекстовых файлов, в частности музыкальных файлов и файлов цифровых изображений. Один вариант осуществления изобретения будет способен обрабатывать нетекстовые файлы в предположении, что метаданные можно подвергать синтаксическому анализу для выделения слов. Это предположение остается в силе для многих типов текстовых файлов, но не для всех.

Анализ релевантности текстов также будет использоваться в настоящем изобретении, в компьютере 239 релевантности текстов. Этот модуль принимает на своем входе ключевые слова 223 вместе со списком 237 неранжированных совпадений и выдает список тех же самых совпадений, сопровождаемых их оценками TR текстовой релевантности, в базу 241 данных (БД) (DB) оценок релевантности. Оценка текстовой релевантности TR вычисляется для каждого документа в списке совпадений и относительно заданных ключевых слов с помощью известной технологии.

Стоит здесь отметить, что простые формы анализа релевантности текстов нежелательны для поиска в Сети, потому что они подвержены введению в заблуждение посредством «спаммирования», т.е. нечестный разработчик Сетевой страницы вводит в эту страницу много копий некоторых ключевых слов, которые обнаруживаются Сетевым поисковиком, но тем не менее невидимы для читателя-человека. Однако спаммирование, вероятно, не является проблемой для персональной поисковой машины по персональному контенту. Пользователь же не будет спаммировать самого себя. Кроме того, с любыми файлами, содержащими спам, которые находят свой путь в собрание пользователя, пользователь разбирается самостоятельно. Следовательно, простые формы анализа релевантности текстов могут быть вполне адекватны для персональной поисковой машины. Однако и более сложные формы тоже можно использовать.

Далее мы обращаемся к компьютеру 205 подобия. Этот процесс происходит в фоновом режиме. Проблема измерения подобия очень близка к проблеме релевантности текстов. В первой задают набор ключевых слов и документ и стараются определить, насколько релевантным является документ к понятию, представленному ключевыми словами. Для вычисления меры подобия задают два документа и нужно определить, какое перекрытие существует между понятиями, рассматриваемыми в одном документе, с понятиями, рассматриваемыми в другом документе. Один вариант осуществления настоящего изобретения использует синтаксический анализатор 203 для проверки документов 201 попарно в фоновом процессе. Синтаксический анализатор распознает слова в паре документов и подает свои результаты в компьютер 205 подобия.

Понятия измерений являются гораздо большей проблемой, нежели синтаксический анализ и подсчет ключевых слов. Однако (опять-таки) существуют простые способы, которые подходят для персональной поисковой машины. Ниже следует простой способ измерения подобия, который будет использоваться в одном варианте осуществления изобретения.

Начинаем со «словаря», а именно с набора слов, который используется в инвертированном индексе. Имеются полезные слова, которые находятся в файлах. (Примерами бесполезных слов являются «стоп»-слова, такие как: артикль, и, он, если и т.п.) Затем для каждого слова w и для каждого файла f синтаксический анализатор подсчитывает число раз N_f(w), когда слово w появлялось в файле f. Далее делим N_f(w) на N_f - общее число слов в файле, обозначая результат n_f(w). Термин n_f(w) называется «профиль слов» файла f.

Подобие S(1,2) между файлом 1 и файлом 2 определяется следующим образом:

S(1,2)=K.

Здесь постоянная К является другим настроечным параметром, который устанавливает шкалу мер подобия. В предпочтительном варианте осуществления изобретения постоянная К равна 1. В этом случае подобие является положительным числом между нулем и единицей. Далее подобие двух идентичных файлов при К=1 точно равно 1.

Как отмечено выше, простота не является обязательно недостатком при поиске и навигации по персональной файловой системе. В любом случае не ожидается, что спаммирование частот слов станет проблемой.

Каждый файл в системе 201 будет иметь вес подобия по отношению к каждому другому файлу. Таким образом, можно ожидать, что граф, сформированный из связей подобия, будет завершенным. (Для завершенного графа каждая вершина (документ) связана с каждой другой.) Однако может случиться, что вес подобия для двух файлов может быть в точности равен нулю (когда эти два файла не имеют общих словарных слов). Можно ожидать, что такие случаи будут редкими. Однако, если имеются какие-либо связи подобия с нулевым весом, граф подобия перестает быть завершенным. (Он остается неотрицательным, т.е. все связи подобия имеют положительные или нулевые веса.) Завершенность графа, однако, не является необходимым условием для получения положительного веса из анализа связей для всех вершин. Вместо этого необходимым условием является то, чтобы граф был «сильно связанным». В сильно связанном графе для любых двух вершин А и В имеется по меньшей один путь из А в В и по меньшей мере один путь (необязательно тот же самый путь) из В в А. Симметричный граф, такой как граф подобия, будет сильно связанным, пока он связан, т.е. пока граф нельзя разбить на несвязанные куски без связей между этими кусками.

О