Алгоритм поиска в массиве PHP / mysql

Question

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

$citysearch = mysql_query("  SELECT city FROM $table WHERE city LIKE '$city' ");

но я не могу найти способ определить, насколько он точен.

Цель будет:
а) найдите слово «Милуоки», если поисковый термин был «милуоки» или что-то подобное.
б) если поисковый термин «запад», верните такие слова, как «Вест Бенд» и «Вестмонт».

Кто-нибудь знает хороший способ сделать это?

Answer 1

Вы должны проверить полнотекстовый поиск в MySQL. Также проверьте Zend-порт проекта Apache Lucene, Zend_Search_Lucene .

Answer 2

Дополнительные поиски привели меня к расстоянию Левенштейна, а затем к Similar_text, который оказался лучшим способом сделать это.

similar_text("input string", "match against this", $pct_accuracy);

сравнивает строки и сохраняет точность как переменную. Расстояние Левенштейна определяет, сколько операций удаления, вставки или замены для одного символа ему потребуется для перехода от одной строки к другой, с учетом веса каждой функции по-разному (например, вы можете сделать так, чтобы заменить ее стоило дороже). символ, чем удалить символ). Это, очевидно, быстрее, но менее точно, чем Similar_text. В других постах, которые я читал в другом месте, упоминалось, что для строк длиной менее 10000 символов функциональной разницы в скорости нет.

Я использовал измененную версию чего-то, что я нашел, чтобы она работала. В итоге сохраняются первые 3 результата (кроме случаев точного соответствия).

$input = $_POST["searchcity"];
$accuracy = 0;
$runner1acc = 0;
$runner2acc = 0;
while ($cityarr = mysql_fetch_row($allcities)) {
  $cityname = $cityarr[1];
  $cityid = $cityarr[0];
  $city = strtolower($cityname);
  $diff = similar_text($input, $city, $tempacc);

  // check for an exact match
  if ($tempacc == '100') {

    // closest word is this one (exact match)
    $closest = $cityname;
    $closestid = $cityid;
    $accuracy = 100;

    break;
  }

  if ($tempacc >= $accuracy) { // more accurate than current leader
    $runner2 = $runner1;
    $runner2id = $runner1id;
    $runner2acc = $runner1acc;
    $runner1 = $closest;
    $runner1id = $closestid;
    $runner1acc = $accuracy;
    $closest  = $cityname;
    $closestid = $cityid;
    $accuracy = $tempacc;
  }
  if (($tempacc < $accuracy)&&($tempacc >= $runner1acc)) { // new 2nd place
    $runner2 = $runner1;
    $runner2id = $runner1id;
    $runner2acc = $runner1acc;
    $runner1 = $cityname;
    $runner1id = $cityid;
    $runner1acc = $tempacc;
  }
  if (($tempacc < $runner1acc)&&($tempacc >= $runner2acc)) { // new 3rd place
    $runner2 = $cityname;
    $runner2id = $cityid;
    $runner2acc = $tempacc;
  }
}

echo "Input word: $input\n<BR>";
if ($accuracy == 100) {
  echo "Exact match found: $closestid $closest\n";
} elseif ($accuracy > 70) { // for high accuracies, assumes that it's correct
  echo "We think you meant $closestid $closest ($accuracy)\n";
} else {
  echo "Did you mean:<BR>";
  echo "$closestid $closest? ($accuracy)<BR>\n";
  echo "$runner1id $runner1 ($runner1acc)<BR>\n";
  echo "$runner2id $runner2 ($runner2acc)<BR>\n";
}

Answer 3

Самый безумный результат с LIKE - это этот "% мужчина", который вернет всю женщину в файл! В случае перечисления, возможно, не слишком плохое решение - продолжать сокращать поисковую стрелку. В вашем случае совпадение будет найдено, когда ваш поиск $ будет таким же коротким, как "milwa".

Answer 4

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

Я писал нечто подобное с нуля несколько раз в прошлом. Если вы пойдете по этому пути, это, вероятно, не то, что вы хотели бы делать в PHP самостоятельно, поскольку каждый запрос будет включать получение всех записей и выполнение ваших расчетов на них. Почти наверняка это будет связано с созданием набора таблиц индексов, соответствующих вашим требованиям.

Например, вам придется придумать правила для того, как вы себе представляете, что «Милуоки» может в конечном итоге записаться как «Милуоки». Моим решением было сделать сжатие гласных и дублирование (не уверен, что это на самом деле поисковые термины). Таким образом, Милуоки будет индексироваться как:

• милуоки
• m_lw__k __
• m_lw_k_

Когда в поисковом запросе указывалось "milwaukee", я запускал тот же процесс для ввода текста, а затем выполнял поиск в таблице индексов для:

SELECT cityId,
       COUNT(*)
  FROM myCityIndexTable
 WHERE term IN ('milwaukee', 'm_lw__k__', 'm_lw_k_')

Когда в поисковом запросе указывалось «milwakee», я запускал тот же процесс для ввода текста, а затем выполнял поиск в таблице индексов для:

SELECT cityId,
       COUNT(*)
  FROM myCityIndexTable
 WHERE term IN ('milwaukee', 'm_lw_k__', 'm_lw_k_')

В случае с Милуоки (правильно написано), для счета будет возвращаться «3».

В случае с Милуаки (написано неправильно) для счетчика будет возвращено «2» (поскольку он не будет соответствовать шаблону m_lw__k__, так как в середине у него был только один гласный).

Если вы сортируете результаты по количеству, вы в конечном итоге соблюдаете одно из ваших правил, что «Милуоки» будет в конечном итоге отсортировано как возможное совпадение, чем «Милуоки».

Если вы хотите построить эту систему в общем виде (как намекает использование в запросе $table), то вам, вероятно, понадобится другая таблица сопоставления где-то там, чтобы сопоставить ваши термины с соответствующей таблицей.

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