Совсем недавно на многих форумах и бесплатных сайтах Рунета появилась возможность совершенно бесплатно скачать систему управления контентом http://www.bitrix.ru/
быстрое определение позиции сайта и ИЦ в поисковиках Rambler, Yandex, Google.ru, Aport в режиме он-лайн
на сайте sitecreator.ru
Результат выводится в виде таблицы. Реально видны конкурирующие сайты (и их тИц).
Эффективный способ обнаружения дубликатов web документов с использованием инвертированного индекса
< вернуться к списку
Сергей Ильинский, Максим Кузьмин, Александр Мелков, Илья Сегалович
"Эффективный способ обнаружения дубликатов web документов с использованием инвертированного индекса."
Аннотация
Развитие Интернета бросает вызов поисковым машинам, так как все больше и больше дубликатов web-документов являются результатами поиска, делая их менее важными для пользователя. Для решения этой проблемы был предложен метод "описательных слов" для выбора схожих документов. Он основан на выборе N слов из индекса для определения "подписи" документа и может быть использован в любом поисковике, основанном на инвертированном индексе. Он сравнивается с методом "каскада". С почти одинаковой точностью алгоритмов этот метод является более эффективным при использовании инвертированного индекса.
Введение
Развитие Интернета бросает вызов поисковым машинам, так как все больше и больше копий web-документов являются результатами поиска, делая их менее важными для пользователя. Происхождение копий довольно разнообразно. Один и тот же документ с одного и того же сервера может иметь различные варианты по техническим причинам - отличающиеся наборы знаков, форматы, а также размещение рекламы или текущей даты. С другой стороны, схожие документы создаются в огромных количествах серверами баз данных, например, сообщениями на форумах, описания продуктов в электронных магазинах и т.д.
Проблема схожих документов исследовалась в работах [1,2,4,5] различных исследовательских групп. Предложенное решение может быть описано следующим образом. Отсканируйте каждый документ, вычислите значения хеш-функции ("отпечатки пальцев"), затем проверьте полученный результат с помощью подходящих критериев и используйте этот уменьшенный набор контрольных сумм ("схема") во всех последующих теоретико-множественных операциях. Фрагментами могут быть предложения [2], последовательность байтов [1], согласных [4] или слов [5]. Были предложены неизменные и переменные эскизы размеров: ряд самых маленьких контрольных сумм и все контрольные суммы, делимые каким-либо целым числом. В работе [3] был предложен метод выбора последовательности слов и улучшения модели векторного пространства для сравнения двуточечных документов.
Метод "каскада" уменьшает размер множества для каждого документа и позволяет упростить выделение кластеров. В тоже время, кластеризация документов остается вычислительно сложной и, как правило, требует инвертирования соотношения документ-каскад. Мы создаем цифровую подпись документа, которая вероятностно неизменна при внесении изменений в документ, таким образом, кластеризация становится ненужной. Все имеющиеся в настоящее время поисковые машины уже имеют базу данных или "инвертированный индекс" всех слов и соответствующих идентификаторов документов. Типичная доступность мировой статистики слова предоставляет приемлемый выбор слов для точного и эффективного решения проблемы. Тогда как соответствующий подход с использованием каскада кажется более сложным из-за большого количества элементов множества каскада.
Постановка задачи
Рассмотрим множество документов. Документом считается последовательность слов. Следовательно, мы имеем дело только с лексической эквивалентностью. Мы предлагаем алгоритм, который составляет "множество копий". Точность алгоритма может быть выражена в терминах возможности двух типов ошибок. "Альфа-ошибкой" считается ситуация, когда алгоритм не определил копию, а "бета-ошибкой" - случай, когда алгоритм предложил неправильную копию. Очевидно, существует компромисс между двумя типами ошибок, поэтому, это не идеальный алгоритм.
Следовательно, необходимо разделить нашу задачу на две части - первая состоит в создании "множества копий", а вторая - в проверке этого множества.
Метод "описательных слов"
Сначала необходимо выбрать некое множество слов N, которое мы назовем "описательным множеством"; выбор слов будет описан ниже.
Для каждого слова давайте установим предельную частоту bi и для каждого документа подсчитаем вектор, где i-тый компонент вектора - единица, если величина относительной частоты i-того слова из "описательного множества" этого документа больше, чем выбранная предельная частота, в другом случае - ноль. Этот бинарный вектор считается нечеткой цифровой подписью документа. Каждый вектор однозначно определяет класс схожих документов. Следовательно, этот уникальный идентификатор может заменять соответствующий вектор. Вектора с 3 или менее словами выше пороговой величины в дальнейшем рассматриваться не будут.
Сформулируем основной критерий выбора слов.
1. Множество слов должно покрывать максимально возможное количество документов.
2. "Качество" слова в смысле, описываемом ниже, должно быть самым лучшим.
3. Количество слов во множестве должно быть минимальным.
"Качество" слова может быть определено как относительная стабильность соответствующего компонента вектора к небольшим изменениям документа. Это значит, что для "хорошего" слова i вероятность перехода (назовем его ) пороговой величины минимальна в случае небольших изменений документа. Очевидно, что вероятность изменения вектора для документа является
Пороговая величина bi , которую мы выбираем, удовлетворяет следующему критерию - величина минимальна при условии, что обе доли (над и под пороговой величиной) не слишком мало. Это условие требуется, чтобы удостовериться, что почти все документы имеют ненулевые векторы. Оптимальное число слов (N) в "описательном множестве" мы определили экспериментальным путем.
Опыты
Мы использовали расстояние Левенштайна, чтобы определить схожесть двух документов. Документы были признаны практически одинаковыми, если разница между ними не превышает 8%. Эти данные были получены в результате опытов, во время которых 6 экспертов высказали 300 утверждений о схожести документов: мы попросили их указать, какие пары идентичны с точки зрения пользователя поисковой машиной. Предварительно из текстов убрали разметку в HTML-формате. В настоящее время наша метрика не принимает во внимание важность несогласованных слов, т.е. частотность слов, которая, как кажется, имеет значение в случае web-магазинов и других документов, созданных на основе баз данных.
Мы взяли 60 миллионов документов-результатов поиска в Yandex [6]. Затем мы создали кластеры копий для разного размера "описательных множеств" и проверили каждый кластер на "фактическую эквивалентность" (8%) как описано выше. Размеры рассматриваемых множеств - от 1600 до 3000 слов. Уменьшение размера "описательного множества" снижает вероятность альфа-ошибки и увеличивает вероятность бета-ошибки. В какой-то момент количество "правильно определенных" копий перестало увеличиваться, в то время как количество ложных копий оставалось незначительным. Выбранное множество состояло из 2000 слов.
Нижеприведенная таблица является сравнением нашего метода с методом "каскада" на одном и том же опыте. "Каскады" были подсчитаны согласно [5] по 10 слов в каскаде, контрольная сумма - 48 бит, коэффициент - 16, пороговая величина сходства - 7/8 множества каскада.
Метод Количество предложенных копий Разница < 8% Разница < 15% Разница < 30% Время обработки данных
Метод "описательных множеств" 22 миллиона 61% 76% 91% ~1.5 часа
Метод "каскада" 19 миллионов 66% 80% 94% ~3.5 часа
Таблица 1. Сравнение метода описательных слов с методом "каскада"
Заключение
Алгоритм использует только инвертированный индекс, который доступен во многих поисковых машинах. Он является очень быстрым. Его очень легко заменить инкрементной версией, т.к. "размытая цифровая подпись" является признанной во всем мире характеристикой документа, и база данных не требует перекластеризации при каждом возрастающем просмотре. При практически одинаковой точности алгоритмов этот метод более эффективен при наличии инвертированного индекса.
Ссылки
1. U. Manber. Finding similar files in a large file system. Proceedings of the 1994 USENIX Conference, pp. 1-10, January 1994.
2. S. Brin, J. Davis, H. Garcia-Molina. Copy Detection Mechanisms for Digital Documents. Proceedings of the ACM SIGMOD Annual Conference, San Francisco, CA, May 1995.
3. N. Shivakumar, H. Garcia-Molina. SCAM: A Copy Detection Mechanism for Digital Documents. Proceedings of the 2nd International Conference on Theory and Practice of Digital Libraries, Austin, Texas, 1995.
4. Nevin Heintze. Scalable Document Fingerprinting. Proceedings of the Second USENIX Workshop on Electronic Commerce, Oakland, California, November 18-21, 1996.
5. Andrei. Z. Broder, Steven. C. Glassman, and Mark. S. Manasse. Syntactic Clustering of the Web. In Proceedings of the Sixth World Wide Web Conference, 1997.
6. http://www.yandex.ru/
site:
If you include [site:] in your query, Google will restrict the results to those websites in the given domain. For instance, [help site:www.google.com] will find pages about help within www.google.com [help site:com] will find pages about help within .com urls. Note there can be no space between the "site:" and the domain.
allintitle:
If you start a query with [allintitle:], Google will restrict the results to those with all of the query words in the title. For instance, [allintitle: google search] will return only documents that have both "google" and "search" in the title.
intitle:
If you include [intitle:] in your query, Google will restrict the results to documents containing that word in the title. For instance, [intitle:google search] will return documents that mention the word "google" in their title, and mention the word "search" anywhere in the document (title or no). Note there can be no space between the "intitle:" and the following word.
Putting [intitle:] in front of every word in your query is equivalent to putting [allintitle:] at the front of your query: [intitle:google intitle:search] is the same as [allintitle: google search].
allinurl:
If you start a query with [allinurl:], Google will restrict the results to those with all of the query words in the url. For instance, [allinurl: google search] will return only documents that have both "google" and "search" in the url.
Note that [allinurl:] works on words, not url components. In particular, it ignores punctuation. Thus, [allinurl: foo/bar] will restrict the results to page with the words "foo" and "bar" in the url, but won't require that they be separated by a slash within that url, that they be adjacent, or that they be in that particular word order. There is currently no way to enforce these constraints.
inurl:
If you include [inurl:] in your query, Google will restrict the results to documents containing that word in the url. For instance, [inurl:google search] will return documents that mention the word "google" in their url, and mention the word "search" anywhere in the document (url or no). Note there can be no space between the "inurl:" and the following word.
Putting "inurl:" in front of every word in your query is equivalent to putting "allinurl:" at the front of your query: [inurl:google inurl:search] is the same as [allinurl: google search].
allinanchor: Note: Not taken directly from Google, but is my definition.
If you start a query with [allinanchor:], Google will restrict the results to those with all of the query words in anchor text pointing to their site. For instance, [allinanchor: google search] will return documents that have both "google" and "search" in anchor text pointing to their site.
Note that [allinanchor:] works on words, not url components. In particular, it ignores punctuation. Thus, [allinanchor: foo/bar] will restrict the results to pages with the words "foo" and "bar" in the anchor text, but won't require that they be separated by a slash within that anchor text, that they be adjacent, or that they be in that particular word order. There is currently no way to enforce these constraints.
inanchor: Note: Not taken directly from Google, but is my definition.
If you include [inanchor:] in your query, Google will restrict the results to documents containing that word in anchor text pointing to their site. For instance, [inanchor:google search] will return documents that have the word "google" in anchor text pointing to their site, and mention the word "search" anywhere in the document. Note there can be no space between the "inanchor:" and the following word.
Putting "inanchor:" in front of every word in your query is equivalent to putting "allinanchor:" at the front of your query: [inanchor:google inanchor:search] is the same as [allinanchor: google search].
cache:
The query [cache:] will show the version of the web page that Google has in its cache. For instance, [cache:www.google.com] will show Google's cache of the Google homepage. Note there can be no space between the "cache:" and the web page url.
If you include other words in the query, Google will highlight those words within the cached document. For instance, [cache:www.google.com web] will show the cached content with the word "web" highlighted.
link:
The query [link:] will list webpages that have links to the specified webpage. For instance, [link:www.google.com] will list webpages that have links pointing to the Google homepage. Note there can be no space between the "link:" and the web page url.
related:
The query [related:] will list web pages that are "similar" to a specified web page. For instance, [related:www.google.com] will list web pages that are similar to the Google homepage. Note there can be no space between the "related:" and the web page url.
info:
The query [info:] will present some information that Google has about that web page. For instance, [info:www.google.com] will show information about the Google homepage. Note there can be no space between the "info:" and the web page url.
define:
The query [define:] will provide a definition of the words you enter after it, gathered from various online sources. The definition will be for the entire phrase entered (i.e., it will include all the words in the exact order you typed them).
stocks:
If you begin a query with the [stocks:] operator, Google will treat the rest of the query terms as stock ticker symbols, and will link to a page showing stock information for those symbols. For instance, [stocks: intc yhoo] will show information about Intel and Yahoo. (Note you must type the ticker symbols, not the company name.)
