管理者がそれらをクリーンアップできるようにするために、一連のフィールドでほぼ重複する値を見つけようとしています。
私が一致している2つの基準があります
- 一方のストリングはもう一方のストリングに完全に含まれており、その長さの少なくとも 1/4 です。
- 文字列の編集距離は、2 つの文字列の合計の長さの 5% 未満です。
疑似 PHP コード:
foreach($values as $value){
$matches = array();
foreach($values as $match){
if(
(
$value['length'] < $match['length']
&&
$value['length'] * 4 > $match['length']
&&
stripos($match['value'], $value['value']) !== false
)
||
(
$match['length'] < $value['length']
&&
$match['length'] * 4 > $value['length']
&&
stripos($value['value'], $match['value']) !== false
)
||
(
abs($value['length'] - $match['length']) * 20 < ($value['length'] + $match['length'])
&&
0 < ($match['changes'] = levenshtein($value['value'], $match['value']))
&&
$match['changes'] * 20 <= ($value['length'] + $match['length'])
)
){
$matches[] = &$match;
}
}
// output matches for current outer loop value
}
可能な限り、比較的高価なstriposおよびlevenshtein関数の呼び出しを減らすようにしました。これにより、実行時間がかなり短縮されました。ただし、O(n^2) 演算として、これはより大きな値のセットに対応できず、配列を単純に反復処理するだけでかなりの量の処理時間が費やされているようです。
操作されている値のいくつかのセットのいくつかのプロパティ
合計 | ストリングス | 文字列あたりの一致数 | | |
ストリングス | マッチで | 平均 | 中央値 | マックス | 時間 |
------+--------------+---------+--------+------+ ----------+
844 | 413 | 1.8 | 1 | 58 | 140 |
593 | 156 | 1.2 | 1 | 5 | 62 |
272 | 168 | 3.2 | 2 | 26 | 10 |
157 | 47 | 1.5 | 1 | 4 | 3.2 |
106 | 48 | 1.8 | 1 | 8 | 1.3 |
62 | 47 | 2.9 | 2 | 16 | 0.4 |
基準をチェックする時間を短縮するために他にできることはありますか。さらに重要なことに、必要な基準チェックの数を減らす方法はありますか (たとえば、入力値を前処理することによって)。選択率が低い？
編集：実装されたソリューション
// $values is ordered from shortest to longest string length
$values_count = count($values); // saves a ton of time, especially on linux
for($vid = 0; $vid < $values_count; $vid++){
for($mid = $vid+1; $mid < $values_count; $mid++){ // only check against longer strings
if(
(
$value['length'] * 4 > $match['length']
&&
stripos($match['value'], $value['value']) !== false
)
||
(
($match['length'] - $value['length']) * 20 < ($value['length'] + $match['length'])
&&
0 < ($changes = levenshtein($value['value'], $match['value']))
&&
$changes * 20 <= ($value['length'] + $match['length'])
)
){
// store match in both directions
$matches[$vid][$mid] = true;
$matches[$mid][$vid] = true;
}
}
}
// Sort outer array of matches alphabetically with uksort()
foreach($matches as $vid => $mids){
// sort inner array of matches by usage count with uksort()
// output matches
}