Ближайшее совпадение для полнотекстового поиска

Question

Я пытаюсь реализовать внутренний поиск для моего веб-сайта, который может указывать пользователям правильное направление в случае неправильного ввода слова, что-то вроде того, что вы имели в виду : в поиске Google.

У кого-нибудь есть идея, как можно провести такой поиск? Как мы можем установить релевантность слова или фразы, которую мы предполагаем, пользователь хотел найти?

• я использую asp.net и sql server 2005 с FTS (fullTextSearch)

Спасибо

Answer 1

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

Одним из таких алгоритмов является расстояние Левенштейна .

Однако не забудьте поискать существующие решения. Я думаю, например Lucene имеет возможность поиска похожих строк.

Кстати, вот соответствующий пост на эту тему: Как работает алгоритм Google «Вы имели в виду?»?

Answer 2

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

Здесь - отличная статья, которая может вам помочь.

Answer 3

почему вы не используете Google Power ?, вы можете использовать их предложить услугу

здесь - пример на c #

Answer 4

С T-SQL Вы можете использовать функцию SOUNDEX для фонетического сравнения слов.

Если вы берете вводимые пользователем данные и затем сравниваете их с другими словами в вашей базе данных по soundex-коду, вы сможете составить список «Вы имеете в виду»? слова.

1008 * Е.Г. *

select SOUNDEX('andrew')
select SOUNDEX('androo')

выдаст одинаковый выход (A536).

В наши дни существуют лучшие алгоритмы, но soundex встроен в сервер sql.

Answer 5

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

Я сделал это с помощью метода ветвей и границ. Позвольте мне выкопать код:

bool matchWithinBound(char* a, char* b, int bound){
  // skip over matching characters
  while(*a && *b && *a == *b){a++; b++;}
  if (*a==0 && *b==0) return true;
  // if bound too low, quit
  if (bound <= 0) return false;
  // try assuming a has an extra character
  if (*a && matchWithinBound(a+1, b, bound-1)) return true;
  // try assuming a had a letter deleted
  if (*b && matchWithinBound(a, b+1, bound-1)) return true;
  // try assuming a had a letter replaced
  if (*a && *b && matchWithinBound(a+1, b+1, bound-1)) return true;
  // try assuming a had two adjacent letters swapped
  if (a[0] && a[1]){
    char temp;
    int success;
    temp = a[0]; a[0] = a[1]; a[1] = temp;
    success = matchWithinBounds(a, b, bound-1);
    temp = a[0]; a[0] = a[1]; a[1] = temp;
    if (success) return true;
  }
  // can try other modifications
  return false;
}

int DistanceBetweenWords(char* a, char* b){
  int bound = 0;
  for (bound = 0; bound < 10; bound++){
    if (matchWithinBounds(a, b, bound)) return bound;
  }
  return 1000;
}