PHP Extraer partes similares de varias cadenas

Question

Estoy tratando de extraer las partes que son similares de varias cadenas.

El propósito de esto es un intento de extraer el título de un libro de múltiples OCRings de la página de título.

Esto se aplica solo al comienzo de la cuerda, los extremos de las cuerdas no necesitan ser recortados y pueden permanecer como están.

Por ejemplo, mis cuerdas podrían ser:

$title[0]='the history of the internet, expanded and revised'; 
$title[1]='the history of the internet'; 
$title[2]='published by xyz publisher the historv of the internot, expanded and'; 
$title[3]='history of the internet'; 

Así que básicamente me quiera recortar cada cuerda de manera que se inicia en el punto de partida más probable. Teniendo en cuenta que puede haber errores de OCR (por ejemplo, "historv", "internot"), pensé que sería mejor tomar el número de caracteres de cada palabra, lo que me daría una matriz para cada cadena (por lo que una matriz multidimensional) con la longitud de cada palabra Esto se puede usar para encontrar coincidencias de ejecución y recortar los inicios de la cadena a la más probable.

Las cuerdas se cortará a:

$title[0]='the history of the internet, expanded and revised'; 
$title[1]='the history of the internet'; 
$title[2]='the historv of the internot, expanded and'; 
$title[3]='XXX history of the internet'; 

así que tengo que ser capaz de reconocer que "la historia de la Internet" (7 2 3 8) es la carrera que coincide con todas las cadenas, y que el preceder a "the" es probablemente correcto ya que ocurre en> 50% de las cadenas y, por lo tanto, el comienzo de cada cadena se recorta a "the" y se agrega un marcador de la misma longitud en la cadena que falta "the".

Hasta ahora no han conseguido:

function CompareSimilarStrings($array) 
    { 
    $n=count($array); 

    // Get length of each word in each string > 
    for($run=0; $run<$n; $run++) 
     { 
     $temp=explode(' ',$array[$run]); 
     foreach($temp as $key => $val) 
     $len[$run][$key]=strlen($val); 
     } 

    for($run=0; $run<$n; $run++) 
     { 

     } 
    } 

Como se puede ver, estoy atascado en la búsqueda de los partidos en ejecución.

¿Alguna idea?

Answer 1

Debería mirar en Smith-Waterman algorithm para la alineación local de cadenas. Es un algoritmo de programación dinámica que encuentra partes de la cadena que son similares en cuanto a que tienen edit distance bajo.

Así que si quieres probarlo, aquí tienes un php implementation of the algorithm.