Wyodrębnij PHP Podobne części z wielu ciągów znaków

Question

Próbuję wyodrębnić części, które są podobne z wielu ciągów.

Celem jest próba wyodrębnienia tytułu książki z wielu OCRings strony tytułowej.

Dotyczy tylko początku napisu, końce strun nie muszą być przycinane i mogą pozostać takie, jakie są.

Na przykład, moje struny może być:

$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'; 

Więc w zasadzie chciałbym przyciąć każdy ciąg tak, że zaczyna się od najbardziej prawdopodobnego punktu wyjścia. Biorąc pod uwagę, że mogą występować błędy OCR (np. "Historv", "internot"), pomyślałem, że najlepiej będzie wziąć liczbę znaków z każdego słowa, które dadzą mi tablicę dla każdego ciągu (czyli tablicy wielowymiarowej) o długości każdego słowa. To może być następnie użyte do znalezienia dopasowań biegowych i przyciąć początki łańcucha do najbardziej prawdopodobnego.

strun należy wyciąć do:

$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'; 

Więc muszę być w stanie rozpoznać, że „historia internet” (7 2 3 8) jest prowadzony który obejmuje wszystkie ciągi, i że poprzedzające "the" jest najprawdopodobniej poprawne, ponieważ występuje w> 50% ciągów znaków, a zatem początek każdego ciągu jest przycinany do "the", a symbol zastępczy o tej samej długości jest dodawany do łańcucha bez "the".

Do tej pory mam:

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++) 
     { 

     } 
    } 

Jak widać, utknąłem na znalezienie uruchomionych mecze.

Wszelkie pomysły?

Answer 1

Powinieneś zajrzeć do Smith-Waterman algorithm dla lokalnego wyrównania ciągu. Jest to algorytm programowania dynamicznego, który znajduje części łańcucha, które są podobne pod tym względem, że mają niską wartość: edit distance.

Jeśli więc chcesz go wypróbować, oto php implementation of the algorithm.