2011-08-01 91 views
21

我正在尋找像strpos()的函數有兩個顯著差異:strpos()與多針?

  1. 爲了能夠接受多個針。我的意思是數以千計的針頭。
  2. 搜索大海撈針中的所有匹配項並返回一組起始位置。

當然,它必須是一個有效的解決方案,不僅僅是通過每個針的循環。我已經通過這個論壇搜查,有這一個類似的問題,比如:

,但他們的幽冥是我期待的。我使用strpos只是爲了更好地說明我的問題,可能完全不同的東西必須用於此目的。

我知道Zend_Search_Lucene,我很感興趣,如果它可以用來實現這個和如何(只是一般的想法)?

非常感謝您的幫助和時間!

+0

你處理什麼樣的數據的預浸比賽?什麼是可能的針頭值?你是否尋找整個單詞或子序列? –

+0

總體目標是什麼? – 2011-08-01 09:47:48

+0

這是爲我的博士論文。我必須在文本中找到所有[命名實體](http://en.wikipedia.org/wiki/Named_entity_recognition)。例如,讓我們假設我有一本所有國家的字典和許多城市中的另一個。我想搜索給那些字典的文本。 –

回答

0

您可以使用正則表達式,它們支持OR操作。然而,與strpos相比,這會讓它變得相當緩慢。

+0

是的,使用正則表達式會使它非常慢特別是對於大量的針。 –

+0

如果你只是多次調用strpos會怎麼樣? – TJHeuvel

+0

你的意思是數千次?以及如何找到所有的事件不只是第一次? –

7

下面是我的策略一些示例代碼:

function strpos_array($haystack, $needles, $offset=0) { 
    $matches = array(); 

    //Avoid the obvious: when haystack or needles are empty, return no matches 
    if(empty($needles) || empty($haystack)) { 
     return $matches; 
    } 

    $haystack = (string)$haystack; //Pre-cast non-string haystacks 
    $haylen = strlen($haystack); 

    //Allow negative (from end of haystack) offsets 
    if($offset < 0) { 
     $offset += $heylen; 
    } 

    //Use strpos if there is no array or only one needle 
    if(!is_array($needles)) { 
     $needles = array($needles); 
    } 

    $needles = array_unique($needles); //Not necessary if you are sure all needles are unique 

    //Precalculate needle lengths to save time 
    foreach($needles as &$origNeedle) { 
     $origNeedle = array((string)$origNeedle, strlen($origNeedle)); 
    } 

    //Find matches 
    for(; $offset < $haylen; $offset++) { 
     foreach($needles as $needle) { 
      list($needle, $length) = $needle; 
      if($needle == substr($haystack, $offset, $length)) { 
       $matches[] = $offset; 
       break; 
      } 
     } 
    } 

    return($matches); 
} 

我實現了一個簡單的蠻力上述方法,將用針和乾草堆(不只是字)的任意組合工作。對於可能更快的算法退房:


其他的解決辦法

function strpos_array($haystack, $needles, $theOffset=0) { 
    $matches = array(); 

    if(empty($haystack) || empty($needles)) { 
     return $matches; 
    } 

    $haylen = strlen($haystack); 

    if($theOffset < 0) { // Support negative offsets 
     $theOffest += $haylen; 
    } 

    foreach($needles as $needle) { 
     $needlelen = strlen($needle); 
     $offset = $theOffset; 

     while(($match = strpos($haystack, $needle, $offset)) !== false) { 
      $matches[] = $match; 
      $offset = $match + $needlelen; 
      if($offset >= $haylen) { 
       break; 
      } 
     } 
    } 

    return $matches; 
} 
+1

好主意!但我擔心算法的共謀。對於乾草堆中的10k個針和10k個字符,它會執行substr()函數的100M個調用。無論如何,我會檢查這一點,讓你知道結果。謝謝! –

+0

@Nikola Obreshkov substr()是內部的,所以它相當快。我的功能可以進行所有優化(預先計算針長度和預鑄針頭)。我想到的另一個選擇是效率低於這個,但我會繼續思考。如果你想節省一些時間,並且你知道所有針都是唯一的,你可以在頂部附近刪除'array_unique()'。 –

+0

感謝您在這個問題上的努力。我認爲 ' //使用strpos如果沒有陣列或只有一個針 if(!is_array($ needles)||(count($ needles)== 1 &&($ needles = $ needle [0] | | true))){ return strpos($ haystack,$ needles,$ offset); } ' 必須被省略,因爲它只會返回第一個匹配項。 –

1

看來你正在尋找整個單詞。在這種情況下,這樣的事情可能會有所幫助。因爲它使用內置的功能,它應該比自定義代碼更快,但是你必須來分析它:

$words = str_word_count($str, 2); 

$word_position_map = array(); 

foreach($words as $position => $word) { 
    if(!isset($word_position_map[$word])) { 
     $word_position_map[$word] = array(); 
    } 
    $word_position_map[$word][] = $position; 
} 

// assuming $needles is an array of words 
$result = array_intersect_key($word_position_map, array_flip($needles)); 

存儲在正確格式的信息(如針)將提高運行時(例如,作爲你不必撥打array_flip)。從str_word_count文檔

注:

對於這個函數,「字」的目的被定義爲包含字母字符,其還可以含有一個區域相關的字符串,但不與「'」就「 - 」字符。

因此,請確保您設置的語言環境正確。

+0

謝謝Felix,我不知道str_word_count()。我將爲上述兩個想法準備一個時間測試。我認爲你的代碼會更快。 –

+0

你知道一些使str_word_count()與uft-8一起工作的方法嗎?我可以做一個類似的功能來做到這一點,但是不會有真正的比較。 –

+0

@Nikola:它應該工作,如果你設置的區域設置正確...看看http://php.net/manual/en/function.setlocale.php。 –

2

我知道這並不回答OP的問題,但想評論,因爲這個網頁是在谷歌的頂部針對與多個針的strpos。這裏有一個簡單的解決方案,這樣做的(再次,這是不特定的OP的問題 - 對不起):

$img_formats = array('.jpg','.png'); 
    $missing = array(); 
    foreach ($img_formats as $format) 
     if (stripos($post['timer_background_image'], $format) === false) $missing[] = $format; 
    if (count($missing) == 2) 
     return array("save_data"=>$post,"error"=>array("message"=>"The background image must be in a .jpg or .png format.","field"=>"timer_background_image")); 

如果2項被添加到$缺陣,這意味着,輸入不符合任何$ img_formats數組中的圖像格式。在這一點上,你知道,你可以返回一個錯誤等,這可以很容易地變成一個小功能:

function m_stripos($haystack = null, $needles = array()){ 
     //return early if missing arguments 
     if (!$needles || !$haystack) return false; 
     // create an array to evaluate at the end 
     $missing = array(); 
     //Loop through needles array, and add to $missing array if not satisfied 
     foreach ($needles as $needle) 
      if (stripos($haystack, $needle) === false) $missing[] = $needle; 
     //If the count of $missing and $needles is equal, we know there were no matches, return false.. 
     if (count($missing) == count($needles)) return false; 
     //If we're here, be happy, return true... 
     return true; 
    } 

回到我們的第一個例子中使用則代替功能:

$needles = array('.jpg','.png'); 
    if (!m_strpos($post['timer_background_image'], $needles)) 
     return array("save_data"=>$post,"error"=>array("message"=>"The background image must be in a .jpg or .png format.","field"=>"timer_background_image")); 

中當然,在函數返回真或假之後你做什麼取決於你。