PHP / algoritmo de búsqueda de matriz mysql

Question

Me gustaría poder usar php search en una matriz (o mejor aún, una columna de una tabla mysql) para una cadena en particular. Sin embargo, mi objetivo es que devuelva la cadena que encuentra y el número de caracteres coincidentes (en el orden correcto) u otra forma de ver qué tan razonables son los resultados de la búsqueda, para que pueda usar esa información para decidir si Quiero mostrar el resultado superior de forma predeterminada o dar opciones de usuario a los primeros. Sé que puedo hacer algo como

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

pero no puedo encontrar una manera de determinar qué tan precisa es.

El objetivo sería:
a) encontrar "Milwaukee" si el término de búsqueda fuera "milwakee" o algo similar.
b) si el término de búsqueda fuera "oeste", devolvería cosas como "West Bend" y "Westmont".

¿Alguien sabe una buena manera de hacer esto?

Answer 1

Más búsquedas me llevaron a la distancia de Levenshtein y luego a similar_text, que resultó ser la mejor manera de hacerlo.

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

compara las cadenas y luego guarda la precisión como una variable. La distancia de Levenshtein determina cuántas funciones eliminar, insertar o reemplazar en un solo carácter necesitaría hacer para pasar de una cadena a la otra, con un margen para ponderar cada función de manera diferente (por ejemplo, puede hacer que cueste más reemplazarlas). un carácter que eliminar un carácter). Aparentemente es más rápido pero menos preciso que similar_text. Otras publicaciones que he leído en otros lugares han mencionado que para cadenas de menos de 10000 caracteres, no hay diferencia funcional en la velocidad.

Terminé usando una versión modificada de algo que encontré para que funcione. Esto termina guardando los 3 primeros resultados (excepto en el caso de una coincidencia exacta).

$input = 
 Más búsquedas me llevaron a la distancia de Levenshtein y luego a similar_text, que resultó ser la mejor manera de hacerlo. 

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


 compara las cadenas y luego guarda la precisión como una variable. La distancia de Levenshtein determina cuántas funciones eliminar, insertar o reemplazar en un solo carácter necesitaría hacer para pasar de una cadena a la otra, con un margen para ponderar cada función de manera diferente (por ejemplo, puede hacer que cueste más reemplazarlas). un carácter que eliminar un carácter). Aparentemente es más rápido pero menos preciso que similar_text. Otras publicaciones que he leído en otros lugares han mencionado que para cadenas de menos de 10000 caracteres, no hay diferencia funcional en la velocidad. 

 Terminé usando una versión modificada de algo que encontré para que funcione. Esto termina guardando los 3 primeros resultados (excepto en el caso de una coincidencia exacta). 

<*>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 2

Debería consultar búsqueda de texto completo en MySQL Consulte también el puerto de Zend del proyecto Apache Lucene, Zend_Search_Lucene .

Answer 3

Esto puede ser muy complicado, y no conozco personalmente ninguna buena biblioteca de terceros, aunque estoy seguro de que existe. Sin embargo, otros pueden sugerir algunas soluciones enlatadas.

He escrito algo similar desde cero algunas veces en el pasado. Si sigue esa ruta, probablemente no sea algo que quiera hacer en PHP por sí solo, ya que cada consulta implicaría obtener todos los registros y realizar sus cálculos en ellos. Es casi seguro que implicará crear un conjunto de tablas de índice que cumplan con sus especificaciones.

Por ejemplo, tendrías que inventar reglas sobre cómo imaginas que "Milwaukee" podría terminar deletreado " milwakee " Mi solución a esto fue hacer compresión de vocales y compresión de duplicación (no estoy seguro si estos son realmente términos de búsqueda). Entonces, milwaukee se indexaría como:

• milwaukee
• m_lw__k__
• m_lw_k_

Cuando llegaba la consulta de búsqueda de "milwaukee", ejecutaba el mismo proceso en la entrada de texto y luego ejecutaba una búsqueda en la tabla de índice para:

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

Cuando llegaba la consulta de búsqueda de "milwakee", ejecutaba el mismo proceso en la entrada de texto y luego realizaba una búsqueda en la tabla de índice para:

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

En el caso de Milwaukee (escrito correctamente), devolvería " 3 " para el recuento.

En el caso de Milwakee (escrito incorrectamente), devolvería " 2 " para el recuento (ya que no coincidiría con el patrón m_lw__k__ ya que solo tenía una vocal en el medio).

Si clasifica los resultados según el recuento, terminaría cumpliendo una de sus reglas, que "Milwaukee" terminaría clasificándose más alto como una posible coincidencia que "Milwakee".

Si desea construir este sistema de manera genérica (como lo sugiere el uso de $ table en la consulta), probablemente necesite otra tabla de mapeo en algún lugar para mapear sus términos a la tabla apropiada.

No estoy sugiriendo que esta sea la mejor (o incluso una buena) forma de hacerlo, solo algo que he hecho en el pasado que podría resultarle útil si planea intentar hacerlo sin un tercero. solución de fiesta.

Answer 4

El resultado más enloquecedor con LIKE es este "% man " ¡Esto devolverá a todas las mujeres en el archivo! En caso de enumerar, tal vez una solución no muy mala es seguir acortando la aguja de búsqueda. En su caso, aparecerá una coincidencia cuando su búsqueda $ sea tan corta como '' milwa ''.