<?php
similar_text(string $string1, string $string2, float &$percent = null): int
// 返回值:匹配字符總長度 (int)
// $percent:引用參數,返回相似度百分比 (0-100)
// 示例
similar_text('aaaa', 'aaaa', $p); // 返回 4, $p=100.0
similar_text('aaaa', 'aaaabbbb', $p); // 返回 4, $p=66.67
similar_text('abcdef', 'aabcdefg', $p); // 返回 6, $p=85.71
?>
原文已部分分析,本文補充完整邏輯與複雜度證明。
**注意**:這是 **最長公共子串 (連續)**,而非最長公共子序列 (LCS, 可不連續)。
max 及在兩字符串中的起始位置 pos1, pos2。雙重循環暴力匹配,複雜度 O(m × n × min(m,n)) ≈ O(n³)。sum = max + left_sum + right_sumpercent = sum * 200.0 / (len1 + len2)// php_similar_str: 找最長公共子串 - O(n^3)
static void php_similar_str(char *t1, int len1, char *t2, int len2, int *pos1, int *pos2, int *max)
{
for (p = t1; p < t1+len1; p++) {
for (q = t2; q < t2+len2; q++) {
for (l = 0; p+l < t1+len1 && q+l < t2+len2 && p[l] == q[l]; l++);
if (l > *max) { *max = l; *pos1 = p-t1; *pos2 = q-t2; }
}
}
}
// php_similar_char: 遞歸累加 - 最壞仍 O(n^3)
static int php_similar_char(char *t1, int len1, char *t2, int len2)
{
php_similar_str(t1, len1, t2, len2, &pos1, &pos2, &max);
if ((sum = max)) {
if (pos1 && pos2) sum += php_similar_char(t1, pos1, t2, pos2); // 左半部
if (pos1+max < len1 && pos2+max < len2)
sum += php_similar_char(t1+pos1+max, len1-pos1-max, t2+pos2+max, len2-pos2-max); // 右半部
}
return sum;
}
<?php
function bench(int $len) {
$s1 = str_repeat('a', $len);
$s2 = str_repeat('a', $len);
$start = microtime(true);
similar_text($s1, $s2, $p);
return microtime(true) - $start;
}
foreach ([100, 200, 500, 1000, 2000] as $len) {
echo "Len $len: " . bench($len) . "s\n";
}
/* 典型輸出 (PHP 8.2):
Len 100: 0.0003s
Len 200: 0.002s
Len 500: 0.03s
Len 1000: 0.25s
Len 2000: 2.1s <-- 指數級增長!
Len 5000: ~30s <-- 不可接受
*/
?>
結論:**嚴禁對長字符串 ( > 500 字符) 使用 similar_text()**,會導致請求超時、CPU 100%。
<?php
$s1 = str_repeat('a', 2000);
$s2 = str_repeat('a', 2000);
$t = microtime(true); similar_text($s1, $s2, $p); echo "similar_text: " . (microtime(true)-$t) . "s\n"; // ~2s
$t = microtime(true); $d = levenshtein($s1, $s2); echo "levenshtein: " . (microtime(true)-$t) . "s\n"; // ~0.001s (快 2000 倍!)
?>
<?php
// levenshtein(string $s1, string $s2, int $costIns, int $costRep, int $costDel): int
// 插入、替換、刪除 的代價權重
$dist = levenshtein('kitten', 'sitting', 1, 1, 1); // 3 (k→s, e→i, +g)
// 應用:拼寫糾錯/模糊搜尋 - 設定替換代價較高,懲罰字符變更
$dist = levenshtein('aple', 'apple', 1, 2, 1); // 插入 'p' 代價 1,替換代價 2
?>
**場景**:用戶輸入「php程式語言」,建議「PHP 程式語言」、「PHP 程式設計」、「PHP 語言教程」。
| 數據量/長度 | 推薦算法 | 實現方式 |
|---|---|---|
| 短文本 (< 50 字)、小詞庫 (< 1萬) | levenshtein() | PHP 直接計算,配合成本權重 |
| 短文本、大詞庫 (10萬+) | Levenshtein Automaton / BK-Tree / Trie + DP | 需 C 擴展或外部服務 (Elasticsearch Fuzzy Query) |
| 長文本/文檔相似度 | SimHash / MinHash / TF-IDF + Cosine / BERT Embedding | Python/Go 微服務 + 向量資料庫 (Milvus/Pinecone) |
| 中文分詞相似度 | 分詞後 Jaccard / Cosine / Edit Distance on Tokens | PHP: composer require jieba/jieba-php + 自定義相似度 |
<?php
class FuzzySuggester
{
private array $dictionary = [];
private int $maxDistance = 2; // 最大編輯距離
public function __construct(array $words, int $maxDistance = 2)
{
$this->dictionary = array_unique(array_map('mb_strtolower', $words));
$this->maxDistance = $maxDistance;
}
public function suggest(string $input, int $limit = 5): array
{
$input = mb_strtolower($input);
$results = [];
foreach ($this->dictionary as $word) {
// 快速長度過濾:長度差 > maxDistance 必然超距離
if (abs(mb_strlen($word) - mb_strlen($input)) > $this->maxDistance) continue;
$dist = levenshtein($input, $word);
if ($dist <= $this->maxDistance) {
$results[$word] = $dist;
}
}
// 按距離升序,距離相同按詞長/詞頻排序
asort($results);
return array_slice(array_keys($results), 0, $limit);
}
}
// 使用
$dict = ['php編程', 'php教程', 'python教程', 'java編程', 'javascript', 'php框架', 'laravel'];
$suggester = new FuzzySuggester($dict, 2);
print_r($suggester->suggest('php程序', 3));
// 可能輸出: ['php編程', 'php教程', 'php框架'] (編輯距離 1 或 2)
?>
composer require jieba/jieba-php
<?php
use Fukuball\Jieba\Jieba;
use Fukuball\Jieba\Finalseg;
Jieba::init();
Finalseg::init();
function chineseSimilarity(string $a, string $b): float
{
$tokensA = Jieba::cut($a); // 分詞陣列
$tokensB = Jieba::cut($b);
// Jaccard 相似係數: 交集大小 / 並集大小
$setA = array_flip($tokensA);
$setB = array_flip($tokensB);
$intersect = array_intersect_key($setA, $setB);
$union = array_merge($setA, $setB);
return count($union) > 0 ? count($intersect) / count($union) : 0;
}
echo chineseSimilarity('PHP 程式語言入門教程', 'PHP 程式設計基礎教學'); // ~0.4-0.6
?>
mb_strlen、array_is_list、match 表達式寫出更優雅的相似度服務。