Pengantar
Cukup sekarang, kondisi pencocokan Anda mungkin terlalu luas. Namun, Anda dapat menggunakan jarak levenshtein untuk memeriksa kata-kata Anda. Mungkin tidak terlalu mudah untuk memenuhi semua tujuan yang diinginkan dengannya, seperti kesamaan suara. Jadi, saya sarankan untuk membagi masalah Anda menjadi beberapa masalah lain.
Misalnya, Anda dapat membuat beberapa pemeriksa khusus yang akan menggunakan input callable yang diteruskan yang membutuhkan dua string dan kemudian menjawab pertanyaan tentang apakah keduanya sama (untuk levenshtein yang akan berjarak lebih kecil dari beberapa nilai, untuk similar_text - beberapa persen kesamaan dll. - terserah Anda untuk menentukan aturan).
Kesamaan, berdasarkan kata
Nah, semua fungsi bawaan akan gagal jika kita berbicara tentang kasus ketika Anda mencari kecocokan sebagian - terutama jika ini tentang kecocokan yang tidak berurutan. Jadi, Anda perlu membuat alat perbandingan yang lebih kompleks. Anda memiliki:
- String data (yang akan ada di DB, misalnya). Sepertinya D =D0 D1 D2 ... Dn
- String pencarian (yang akan menjadi input pengguna). Sepertinya S =S0 S1 ... Sm
Di sini simbol ruang berarti sembarang ruang (saya berasumsi bahwa simbol ruang tidak akan memengaruhi kesamaan). Juga n > m . Dengan definisi ini masalah Anda adalah tentang - untuk menemukan kumpulan m kata dalam D yang akan mirip dengan S . Dengan set Maksud saya urutan yang tidak berurutan. Oleh karena itu, jika kita akan menemukan urutan seperti itu di D , lalu S mirip dengan D .
Jelas, jika n < m maka input berisi lebih banyak kata daripada string data. Dalam hal ini Anda mungkin berpikir bahwa keduanya tidak serupa atau bertindak seperti di atas, tetapi beralihlah data dan input (namun, terlihat sedikit aneh, tetapi dapat diterapkan dalam beberapa hal)
Implementasi
Untuk melakukan hal itu, Anda harus dapat membuat set string yang merupakan bagian dari m kata-kata dari D . Berdasarkan pertanyaan ini
saya Anda dapat melakukannya dengan:
protected function nextAssoc($assoc)
{
if(false !== ($pos = strrpos($assoc, '01')))
{
$assoc[$pos] = '1';
$assoc[$pos+1] = '0';
return substr($assoc, 0, $pos+2).
str_repeat('0', substr_count(substr($assoc, $pos+2), '0')).
str_repeat('1', substr_count(substr($assoc, $pos+2), '1'));
}
return false;
}
protected function getAssoc(array $data, $count=2)
{
if(count($data)<$count)
{
return null;
}
$assoc = str_repeat('0', count($data)-$count).str_repeat('1', $count);
$result = [];
do
{
$result[]=array_intersect_key($data, array_filter(str_split($assoc)));
}
while($assoc=$this->nextAssoc($assoc));
return $result;
}
-jadi untuk array apa pun, getAssoc() akan mengembalikan larik pilihan tidak berurutan yang terdiri dari m item masing-masing.
Langkah selanjutnya adalah tentang urutan dalam seleksi yang dihasilkan. Kita harus mencari keduanya Niels Andersen dan Andersen Niels di D . kami rangkaian. Oleh karena itu, Anda harus dapat membuat permutasi untuk array. Ini masalah yang sangat umum, tetapi saya akan memasukkan versi saya di sini juga:
protected function getPermutations(array $input)
{
if(count($input)==1)
{
return [$input];
}
$result = [];
foreach($input as $key=>$element)
{
foreach($this->getPermutations(array_diff_key($input, [$key=>0])) as $subarray)
{
$result[] = array_merge([$element], $subarray);
}
}
return $result;
}
Setelah ini, Anda dapat membuat pilihan m kata dan kemudian, permutasi masing-masing, dapatkan semua varian untuk dibandingkan dengan string pencarian S . Perbandingan itu setiap kali akan dilakukan melalui beberapa panggilan balik, seperti levenshtein . Ini contohnya:
public function checkMatch($search, callable $checker=null, array $args=[], $return=false)
{
$data = preg_split('/\s+/', strtolower($this->data), -1, PREG_SPLIT_NO_EMPTY);
$search = trim(preg_replace('/\s+/', ' ', strtolower($search)));
foreach($this->getAssoc($data, substr_count($search, ' ')+1) as $assoc)
{
foreach($this->getPermutations($assoc) as $ordered)
{
$ordered = join(' ', $ordered);
$result = call_user_func_array($checker, array_merge([$ordered, $search], $args));
if($result<=$this->distance)
{
return $return?$ordered:true;
}
}
}
return $return?null:false;
}
Ini akan memeriksa kesamaan, berdasarkan panggilan balik pengguna, yang harus menerima setidaknya dua parameter (yaitu string yang dibandingkan). Anda juga mungkin ingin mengembalikan string yang memicu pengembalian positif panggilan balik. Harap perhatikan, bahwa kode ini tidak akan membedakan huruf besar dan kecil - tetapi mungkin Anda tidak menginginkan perilaku seperti itu (maka ganti saja strtolower() ).
Contoh kode lengkap tersedia di daftar ini (Saya tidak menggunakan kotak pasir karena saya tidak yakin berapa lama daftar kode akan tersedia di sana). Dengan contoh penggunaan ini:
$data = 'Niels Faurskov Andersen';
$search = [
'Niels Andersen',
'Niels Faurskov',
'Niels Faurskov Andersen',
'Nils Faurskov Andersen',
'Nils Andersen',
'niels faurskov',
'niels Faurskov',
'niffddels Faurskovffre'//I've added this crap
];
$checker = new Similarity($data, 2);
echo(sprintf('Testing "%s"'.PHP_EOL.PHP_EOL, $data));
foreach($search as $name)
{
echo(sprintf(
'Name "%s" has %s'.PHP_EOL,
$name,
($result=$checker->checkMatch($name, 'levenshtein', [], 1))
?sprintf('matched with "%s"', $result)
:'mismatched'
)
);
}
Anda akan mendapatkan hasil seperti:
Testing "Niels Faurskov Andersen" Name "Niels Andersen" has matched with "niels andersen" Name "Niels Faurskov" has matched with "niels faurskov" Name "Niels Faurskov Andersen" has matched with "niels faurskov andersen" Name "Nils Faurskov Andersen" has matched with "niels faurskov andersen" Name "Nils Andersen" has matched with "niels andersen" Name "niels faurskov" has matched with "niels faurskov" Name "niels Faurskov" has matched with "niels faurskov" Name "niffddels Faurskovffre" has mismatched
-di sini adalah demo untuk kode ini, untuk berjaga-jaga.
Kompleksitas
Karena Anda tidak hanya peduli tentang metode apa pun, tetapi juga tentang - seberapa bagusnya, Anda mungkin memperhatikan, bahwa kode tersebut akan menghasilkan operasi yang cukup berlebihan. Maksudku, setidaknya, generasi bagian string. Kompleksitas di sini terdiri dari dua bagian:
- Bagian pembuatan bagian string. Jika Anda ingin membuat semua bagian string - Anda harus melakukan ini seperti yang saya jelaskan di atas. Poin yang mungkin untuk ditingkatkan - pembuatan set string yang tidak berurutan (yang datang sebelum permutasi). Tapi saya masih ragu itu bisa dilakukan karena metode dalam kode yang disediakan akan menghasilkannya bukan dengan "brute-force", tetapi karena dihitung secara matematis (dengan kardinalitas
) - Bagian pemeriksaan kesamaan. Di sini kompleksitas Anda tergantung pada pemeriksa kesamaan yang diberikan. Misalnya,
similar_text()memiliki kompleksitas O(N), sehingga dengan set perbandingan yang besar akan sangat lambat.
Tetapi Anda masih dapat meningkatkan solusi saat ini dengan memeriksa dengan cepat. Sekarang kode ini pertama-tama akan menghasilkan semua sub-urutan string dan kemudian mulai memeriksanya satu per satu. Dalam kasus umum Anda tidak perlu melakukan itu, jadi Anda mungkin ingin menggantinya dengan perilaku, ketika setelah membuat urutan berikutnya akan segera diperiksa. Kemudian Anda akan meningkatkan kinerja untuk string yang memiliki jawaban positif (tetapi tidak untuk string yang tidak cocok).
