PHP/mysql数组搜索算法-解网

问：

我希望能够使用 php 搜索数组（或者更好的是，mysql 表的一列）来搜索特定字符串。但是，我的目标是让它返回它找到的字符串和匹配字符的数量（以正确的顺序）或其他方式来查看搜索结果的合理性，因此我可以利用该信息来决定是否要默认显示顶部结果或为用户提供前几个选项。我知道我可以做这样的事情

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

但我想不出一种方法来确定它的准确性。

目标是：
a）如果搜索词是“milwakee”或类似词，则找到“密尔沃基”。
b）如果搜索词为“west”，则返回“West Bend”和“Westmont”等内容。

有人知道这样做的好方法吗？

php mysql 匹配

我过去曾多次从头开始写过类似的东西。如果你沿着这条路走下去，它可能不是你想在PHP中单独做的事情，因为每个查询都会涉及获取所有记录并对它们执行计算。几乎可以肯定的是，这将涉及创建一组符合您的规范的索引表。

例如，你必须想出一些规则，说明你如何想象“密尔沃基”最终会拼写为“milwakee”。我的解决方案是进行元音压缩和重复压缩（不确定这些是否真的是搜索词）。因此，密尔沃基将被索引为：

密尔沃基
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”作为计数。

在Milwakee（拼写错误）的情况下，它将返回“2”作为计数（因为它与模式不匹配，因为它中间只有一个元音）。m_lw__k__

如果你根据计数对结果进行排序，你最终会满足你的一个规则，即“密尔沃基”最终会被排序为比“米尔韦克”更高的可能匹配项。

如果你想以一种通用的方式构建这个系统（正如你在查询中使用所暗示的那样），那么你可能需要另一个映射表来将你的术语映射到适当的表。$table

我并不是说这是最好的（甚至是一个很好的）方法，只是我过去做过的事情，如果你打算在没有第三方解决方案的情况下尝试这样做，可能会对你有用。

3赞 Brian Fisher 1/13/2009 #2

您应该查看MySQL中的全文搜索。另请查看 Zend 移植的 Apache Lucene 项目，Zend_Search_Lucene。

2赞 Daniel Beder 1/16/2009 #3

更多的搜索将我带到了Levenshtein距离，然后到达了similar_text，这被证明是最好的方法。

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

比较字符串，然后将精度保存为变量。Levenshtein 距离决定了从一个字符串到另一个字符串需要对单个字符执行多少个删除、插入或替换函数，并允许以不同的方式对每个函数进行加权（例如，您可以使替换字符的成本高于删除字符的成本）。它显然比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";
}

0赞 alberto 1/23/2010 #4

LIKE 最令人抓狂的结果是这个“%man”，这将返回文件中的所有女人！在上市的情况下，也许一个不太糟糕的解决方案是继续缩短搜索针。在您的情况下，当您的搜索 $ 与“milwa”一样短时，会出现匹配项。

上一个：正则表达式 - 仅当字符串包含任何字母字符时才匹配字符串

下一个：正则表达式模式 - 允许字母数字，一堆特殊字符，但不允许特定的字符序列

PHP/mysql数组搜索算法

PHP/mysql array search algorithm

评论