緩存鍵查找 - 找到「最接近」或相同的鍵

Question

編輯：我以一種實現不可知的方式接近了這個問題，然而這裏是我所追求的內容。

我有一組功能，即執行讀取和寫入對數組操作，允許的語法如下：

$map->{'foo.bar.baz'}; // same as $array['foo']['bar']['baz']; 

即使在敏感的錯誤報告的環境中，沒有通知被扔在缺乏有針對性的數組元素，而不是返回null。無論如何，爲了提高訪問性能，我已經爲讀取方法添加了緩存功能。

緩存無效（和清除）無論何時進行寫操作，但反覆（在這一點上相同的元素）表現出相當的性能提升讀取。緩存的「值」是對數組元素的引用，而不是元素值的副本。

通過分解字符串（數組元素路徑）如foo.bar.baz發現（如果它存在）$array['foo']['bar']['baz']迭代的（多個）功能的工作。

現在高速緩存是一個簡單的路徑關聯數組（鍵）參考所述給定陣列的適當元件，如：

'foo' => &$array['foo'], 
'foo.bar' => &$array['foo']['bar'], 

然而，我想我可以進一步改善高速緩存性能通過查找給定路徑的最接近父親的引用，而不是特定路徑。例如：

// given 
$map->{'foo.bar'}; // read operation 

// followed by 
$map->{'foo.bar.baz.zip'}; // another read operation 

由於沒有密鑰緩存中的foo.bar.baz.zip存在，它必須執行一個全新的獲取對數組。我希望我可以利用存儲的參考foo.bar的優勢，只是執行baz.zip對此的提取。

所有這些加起來找到最接近的字符串匹配，包括正在讀取的當前路徑。

levenshtein()似乎是一個合適的可能性（由@mfonda作爲perscribed - 謝謝你的方式）如果包裹有一些初步的檢查，以避免不必要的重複，但我已經注意到，由於方式，它的diff 2它有時會返回無效匹配，發現foo.zoo爲foo.bar.zoo而不是foo.bar。

---

快速的;我在尋找最快捷的方式來匹配字符串，從字符串數組找到最接近（或相同）（鍵），由爲何我的意思是：

// given 
$string = 'foo.bar.baz'; 

// and 
$list_1 = array(
    'foo' => null 
    'foo.bar.baz.zip' => null, 
); 

// and 
$list_2 = array(
    'foo' => null, 
    'foo.bar' => null, 
    'foo.goo.baz' => null, 
); 

// and 
$list_3 = array(
    'foo.bar.baz' => null, 
    'foo.bar.baz.zip' => null, 
); 

// yields 
echo magic_match($string, $list_1); // foo 
echo magic_match($string, $list_2); // foo.bar 
echo magic_match($string, $list_3); // foo.bar.baz 

字符串「親近「由最長的字符串決定，不超過匹配的檢查字符串。因此abc檢查對照a和abcd匹配a，因爲abcd超過檢查的長度。

我正在做一些測試，但我確定SO社區中的PHP開發者已經設計了一些東西。

看來（不幸）在PHP中沒有本地函數來做到這一點;之間strstr(),preg_grep()（哪些不做這項工作反正）和奇怪的替代組合，沒有什麼似乎特別快。

---

在這一點上，以確定是否存在$string準確（或不），我們可以用開始：

if(!isset($list[$string])){ 
    // proceed with processing to find closest 
}else{ 
    // identical found 
} 

由於字符串分隔與.，我們可以explode()字符串並逐步崩潰：

$parts = explode('.', $string); 
while(!empty($parts)){ 
    if(isset($list[$string = implode('.', $parts))]){ 
     break; 
    } 
    array_pop($parts); 
} 

但是，持續重新爆炸字符串通過迭代可以證明代價高昂。

Answer 1

那麼你的匹配標準有點模糊。所以你可能會自己去做。我看到有不同的情況，這取決於長度。因此，如何：

function magic_match($str, $list) { 
    $scores = array(); 
    foreach($list as $item) { 

     if (strlen($str) > strlen($item) { 
     // one type of compare 
     $scores[] = array($item, $score); 
     } 
     else { 
     // other type 
     $scores[] = array($item, $score); 
     } 
    } 

    // return item with highest score 
} 

Answer 2

你可能想看看similar_text()或levenshtein()。這些函數將給你一個兩個字符串相似程度的度量。基於此，您可以選擇最接近的匹配。