Trích xuất PHP Các phần tương tự từ nhiều chuỗi

Question

Tôi đang cố gắng trích xuất các phần tương tự với nhiều chuỗi.

Mục đích của việc này là một nỗ lực để trích xuất tiêu đề của một cuốn sách từ nhiều OCRings của trang tiêu đề.

Điều này chỉ áp dụng cho phần đầu của chuỗi, các đầu của chuỗi không cần phải cắt và có thể giữ nguyên.

Ví dụ, các chuỗi của tôi có thể là:

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

Vì vậy, về cơ bản tôi muốn cắt mỗi chuỗi để nó bắt đầu từ điểm xuất phát có thể xảy ra nhất. Xem xét rằng có thể có lỗi OCR (ví dụ: "historyv", "internot") tôi nghĩ tốt nhất là lấy số ký tự từ mỗi từ, điều này sẽ cho tôi một mảng cho mỗi chuỗi (vì vậy mảng đa chiều) với độ dài của mỗi từ. Điều này sau đó có thể được sử dụng để tìm các trận đấu đang chạy và cắt các phần đầu của chuỗi thành nhiều khả năng nhất.

Các chuỗi nên được cắt theo:

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

Vì vậy, tôi cần để có thể nhận ra rằng "lịch sử của Internet" (7 2 3 8) là thời gian mà phù hợp với tất cả các chuỗi, và rằng trước "the" có lẽ là đúng khi nhìn thấy khi nó xảy ra trong> 50% của chuỗi, và do đó đầu của mỗi chuỗi được cắt thành "the" và một trình giữ chỗ có cùng độ dài được thêm vào chuỗi bị thiếu "the".

Cho đến nay tôi đã có:

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

     } 
    } 

Như bạn thấy, tôi bị mắc kẹt vào việc tìm kiếm các trận đấu chạy.

Bất kỳ ý tưởng nào?

Answer 1

Bạn nên xem xét Smith-Waterman algorithm để căn chỉnh chuỗi cục bộ. Nó là một thuật toán lập trình động mà tìm thấy các phần của chuỗi tương tự ở chỗ chúng có mức thấp edit distance.

Vì vậy, nếu bạn muốn dùng thử, dưới đây là php implementation of the algorithm.