В естественном языке обработка в алгоритм шинглова представляет собой набор уникальной черепицы (поэтому н-грамм ) , каждый из которых состоит из смежных подпоследовательностей из маркеров в пределах документа , которые затем могут быть использованы для установления подобия между документами . Символ w обозначает количество жетонов в каждой выбранной или решенной черепице.
Таким образом, документ «роза есть роза есть роза» можно максимально токенизировать следующим образом:
- (а, роза, есть, а, роза, есть, а, роза)
Множество всех смежных последовательностей 4 маркеров (таким образом 4 = п , таким образом 4- г ) является
- {(а, роза, есть, а), (роза, есть, а, роза), (есть, а, роза, есть), (а, роза, есть, а), (роза, есть, а, роза) } Которая затем может быть уменьшена или максимально покрыта черепицей в данном конкретном случае до {(a, rose, is, a), (rose, is, a, rose), (is, a, rose, is)}.
Сходство
Для данного размера черепицы степень, в которой два документа A и B похожи друг на друга, может быть выражена как отношение величин пересечения и объединения их черепицы , или
где | A | - размер набора A. Сходство - это число в диапазоне [0,1], где 1 указывает, что два документа идентичны. Это определение идентично коэффициенту Жаккара, описывающему сходство и разнообразие наборов выборок.
Смотрите также
- Анализ концепций (альтернативный метод расчета сходства документов с большей вычислительной сложностью, но в котором мера более точно моделирует восприятие сходства документов человеком)
- N-грамм
- к-мер
- MinHash
- Прокручивающийся хеш
- Отпечаток пальца рабина
- Векторная модель пространства
- Модель мешка слов
Рекомендации
- (Манбер 1993) Поиск похожих файлов в большой файловой системе . Еще не употребляет термин «черепица».
- (Бродер, Глассман, Манассе и Цвейг, 1997 г.) Синтаксическая кластеризация Интернета . Техническая нота SRC № 1997-015.
Внешние ссылки
- Мэннинг, Кристофер Д.; Рагхаван, Прабхакар; Шютце, Хинрих (7 июля 2008 г.). "шинглинг" . Введение в поиск информации . Издательство Кембриджского университета. ISBN 978-1-139-47210-4.