Какой алгоритм использует freebase для сопоставления по имени?

Question

Я пытаюсь создать локальную версию API поиска FreeBase, используя их четырехсторонние дампы. Мне интересно, какой алгоритм они используют для сопоставления имен? Например, если вы зайдете на freebase.com и введете "Поход", вы получите

• "Апо Туризм Общество"
• "Пеший туризм"
• "Поход по Грузии"
• "Поход Вирджинии по национальным лесам"
• "Тропа"

Answer 1

Ух ты, много догадок! Надеюсь, я не слишком мутлю воду, не догадываясь.

Коробка автозаполнения в основном работает на Freebase Suggest, которая, в свою очередь, работает на сервисе поиска Freebase. Строки, которые индексируются службой поиска для сопоставления, включают в себя: 1) имя, 2) все псевдонимы на данном языке, 3) текст ссылки на якорь из соответствующих статей Википедии и 4) идентификаторы (называемые ключами в Freebase), которые включают в себя элементы как заголовки статей Википедии (и перенаправления).

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

Так что это дает вам небольшое представление о том, как работает их служба, но почему бы не создать поисковую службу, которая делает то, что вам нужно, так как вы все равно начинаете с нуля?

Кстати, перед Google поисковая реализация Metaweb была основана на топе Lucene, так что вы можете определенно сделать хуже, чем использовать это в качестве отправной точки. Вы можете прочитать некоторые детали в архиве списка рассылки

Answer 2

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

Что касается алгоритма, я считаю следующую статью хорошим обзором

Зобель и Моффат (2006): "Перевернутые файлы для систем текстового поиска".

Answer 3

Скорее всего это три с лексикографическим порядком.

Answer 4

Существует несколько доступных алгоритмов: Бойер-Мур, Смит-Уотерман-Гото, Кнут Моррисс-Пратт и т. Д. Вы также можете проверить алгоритмы редактирования расстояний, такие как Левенштейн. Вам нужно будет поиграть, чтобы увидеть, что лучше всего подходит для вашей цели.

Реализация таких алгоритмов - библиотека Simmetrics Университета Шеффилда.