Lớp PHP này, tìm kiếm gần đúng. phps, cung cấp tìm kiếm văn bản không chính xác [thường được gọi là tìm kiếm mờ hoặc khớp gần đúng]
Nó cho phép bạn chỉ định ngưỡng khoảng cách chỉnh sửa Levenshtein, tôi. e. một giới hạn lỗi cho một trận đấu. Ví dụ: tìm kiếm kamari với ngưỡng 1 lỗi sẽ khớp với kamari, kamari, kaMari và kamar nhưng không khớp với kaNar
Mã này được tối ưu hóa để tìm kiếm lặp lại cùng một chuỗi, e. g. duyệt qua các hàng của cơ sở dữ liệu
$search = new Approximate_Search[ $patt, $max_err ]; if [ $search->too_short_err ] $error = "Unable to search - use longer pattern " . "or reduce error tolerance."; while[ $text = /* get some more text */] { $matches = $search->search[ $text ]; while[ list[$i,] = each[$matches]] print "Match that ends at $i.\n"; }
VÁ LỖI. 2006-08-27
Phiên bản trước có một lỗi nhỏ trong một số trường hợp [khá hiếm] khiến mã không tìm thấy kết quả khớp
Chương trình về cơ bản bao gồm hai giai đoạn và một số tối ưu hóa. Không đi vào chi tiết, đây là một tổng quan ngắn về ý tưởng
Giả sử chúng ta có một mẫu tìm kiếm dài n ký tự với k lỗi được phép
- Tỉa / lọc. Đầu tiên phân chia mẫu tìm kiếm thành k+2 phần. Theo nguyên tắc tổ hợp [của tổ hợp], ít nhất 2 trong số các phần này phải nguyên vẹn trong mỗi lần xuất hiện của mẫu. Chúng tôi tìm kiếm toàn văn cho những phần này trước và loại bỏ ngay những phần của văn bản không chứa ít nhất 2 trong số các mẫu đủ gần nhau và theo đúng thứ tự
- tìm kiếm tốt. Đối với các ứng cử viên còn lại, hãy thực hiện tìm kiếm tốt hơn bằng cách sử dụng máy trạng thái không xác định [NFA] hình lưới [n+1] x [k+1] có các cạnh ngang biểu thị các ký tự khớp, bổ sung các cạnh dọc và xóa các cạnh chéo. Điều này hơi khó giải thích nếu không có một số bản vẽ, vì vậy tôi khuyên bạn nên xem qua Baeza-Yates & Navarro chẳng hạn. "Kết hợp chuỗi gần đúng nhanh hơn". Nó mô tả một phương pháp tối ưu hóa ở mức rất thấp mà tôi không sử dụng [vì nó có thể chậm hơn trong PHP] nhưng nó cũng giải thích khá rõ về phiên bản cơ bản
Đây là phần mềm miễn phí; . 1 hoặc [tùy chọn của bạn] bất kỳ phiên bản nào sau này
Recursive algorithm usually is very elegant one. I found a way to get better precision without the recursion. Imagine two different [or same] length ribbons with letters on each. You simply shifting one ribbon to left till it matches the letter the first.
function similarity[$str1, $str2] {
$len1 = strlen[$str1];
$len2 = strlen[$str2];
$max = max[$len1, $len2];
$similarity = $i = $j = 0;
while [[$i < $len1] && isset[$str2[$j]]] {
if [$str1[$i] == $str2[$j]] {
$similarity++;
$i++;
$j++;
} elseif [$len1 < $len2] {
$len1++;
$j++;
} elseif [$len1 > $len2] {
$i++;
$len1--;
} else {
$i++;
$j++;
}
}
return round[$similarity / $max, 2];
}
$str1 = '12345678901234567890';
$str2 = '12345678991234567890';
________số 8
Kết hợp mờ là một cách rất hiệu quả để sửa lỗi cho đầu vào của người dùng, ví dụ: nếu bạn cần khớp từ khóa do người dùng cung cấp với các tùy chọn trong cơ sở dữ liệu. Trong trường hợp cụ thể này, bạn có thể sử dụng các hàm SOUNDEX của mysql, nhưng chúng có những thiếu sót đáng kể như không thể phân biệt các chuỗi dài.
Một cách khác là sử dụng khoảng cách levenshtein. Hàm dựng sẵn này ước tính số lượng thay thế tối thiểu cần thiết để chuyển từ chuỗi A sang chuỗi B. Mặc dù không nhanh lắm, nhưng nó có thể được sử dụng như một cách dễ dàng để cho phép kết hợp mờ mà không cần cài đặt gói hoặc plugin của bên thứ ba.
Mã số.
bao gồm đoạn mã sau trong chương trình php của bạn.
function fuzzy_match[$query,$target,$distance] { ## set max substitution steps if set to 0 if [$distance == 0] { $length = strlen[$query]; if [$length > 10] { $distance = 4; } elseif [$length > 6] { $distance = 3; } else { $distance = 2; } } $lev = levenshtein[strtolower[$query], strtolower[$target]]; if [$lev 1, 'distance' => $lev, 'max_distance' => $distance]; } else { return array['match' => 0, 'distance' => $lev, 'max_distance' => $distance]; } }
Cách sử dụng
Hàm trả về một mảng chứa kết quả, khoảng cách và max_allowed_ distance
đối sánh mờ levenshtein PHP Tìm kiếm