А зачем хранить дерево?
Если предполагается искать только по именам файлов (или по полному пути) то можно представить файл как документ состоящий из слов которые содержатся в имени файла. И строить индекс по этим словам.
Кажется понял. Т.е. Вы предпологаете что документы разной длины всегда различны если они не находятся в пределах одного ранга.
Да, надо еще напомнить начальству что поиск с учетом морфологии потребует в 3-4 раза больше серверов, чем поиск без оной :)
Ведь смысл в шинглах вычислить их для каждого вновь добавляемого документа один раз и сохранить только кратные некоторому числу для последующего сравнения, тем самым съэкономив ресурсы машины.
А так, при поиске документа 3-го ранга среди ранее сохраненных шинглах документов 1-х рангов прийдется либо пересчитывать шинглы "на лету" для всех документов 1-го ранга, либо хранить все шинглы и при поиске брать только кратные искомому.
Я имею ввиду ситуацию, когда документы добавляются в коллекцию в произвольном порядке (не в порядке возрастания/убывания их длины), что характерно для большинства поисковых машин.
А если прийдется сравнивать наоборот, 3-й ранг (шинглы кратны 40) с 1-м рангом (шинглы кратны 10), ведь 40 не кратно 10?
Думаю будут погрешности на "границах рангов", поясню на примере:
Имеем ранги:
1-й ранг от 0 до 99 слов, отбираются шинглы с кратные (по значению) 10
2-й ранг от 100 до 150 слов, отбираются шинглы кратные 15
Имеем два документа с отличием в одно слово:
1-й документ содержит 99 слов (1-й ранг)
2-й документ содержит 100 слов (2-й ранг)
В результате для 1-го документа отберутся шинглы кратные 10, для 2-го кратные 15. Получается шинглы не совпадут.
Действительно так проще.
Мне кажется так работать не будет, смысл выбирать не каждый 10 шингл, а каждый шингл хеш значение которого кратно 10. Т.е. для двух документов одинаковой длины количество отобраных шинглов может быть различным.
Мне это представляется примерно так:
1) Берется контент страницы освобожденный от тегов
2) Если размер страницы меньше некого значения, контент страницы циклически размножается до достижения нужного размера
3) Для страницы вычисляются набор шинглов
4) Из набора шинглов отбираются только кратные некому числу, т.е. их будет не больше чем это число
5) Для каждого полученого шингла ищем дубликат среди хранилища шинглов уже ВСЕХ ранее добавленных страниц
6) Ищем документы у которых совпадает один или несколько шинглов с искомым (необходимое количество совпадений шинглов можно выяснить эксперементально на реальных данных).
7) Для надежности сравниваем полученный список документов с искомым при помощи методов нечеткого сравнения.
8) Если решили что дубликатов документа ранее несуществовало - ДОБАВЛЯЕМ его шинглы в некое хранилище по которому мы ищем в п. 5.
п. 3 - какую хеш функцию подобрать?
п. 4 - неясно какое это должно быть число?
п. 5 - мне кажется что такой поиск не займет много времени, на небольших объемах подойдет даже sql база.
п. 6 - сколько должно быть совпадений шинглов чтобы документы считать идентичными?
Если я правильно понимаю, то метод шинглов позволяет получить одно или несколько хеш значений для каждого документа характеризующих часть документа.
Тогда при добавлении нового документа в индекс, для него вычисляются эти хеш значения, которые ищутся среди хеш значений уже существующих в индексе документов. В результате поиска получается ограниченный набор документов "вероятно похожих" на искомый. Наверно это не сильно ресурсоемкий способ.
На последнем этапе, для каждого документа из полученного списка "вероятно похожих" можно вычислить редакционное расстояние, например методом Левенштейна.
Наверное кроме как полным перебором никак не получится.
Т.е. по шаблону (поиск* запрос*) находятся все слова из словаря, затем для каждого слова извлекается постлист из индекса, после чего полученные постлисты объединяются по OR.
