發現號的頻繁序列中的陣列

Question

陣列(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32)

號碼的頻繁序列將(3, 5) f=2 + (4, 7, 13) f=2

任何算法或僞代碼，找到了嗎？

更新（1）：

如果(7, 13)也發生將被包含在最長的一個通過更新它的頻率，從而

(4, 7, 13) f=3等等...

更新（2）：

在(1,2,3,4,1,2,3,4,1,2,7,8,7,8,3,4,3,4,1,2)情況下，輸出應該是(1,2,3,4) & (3,4,1,2)

& (7,8)，要清楚考慮每個號碼作爲一個詞，你想找到最頻繁的短語

所以經常可以看到在很多短語相同的字或詞，但如果任何的短語是子-string用於任何其他

短語（多個）不應當被認爲是一個短語，但將更新每個短語的頻率包括它

Answer 1

** 編輯 **：稍微好一點的實現，現在也返回頻率的頻道，並具有較好的序列過濾器。

function getFrequences($input, $minimalSequenceSize = 2) { 
    $sequences = array(); 
    $frequences = array(); 

    $len = count($input); 
    for ($i=0; $i<$len; $i++) { 
     $offset = $i; 

     for ($j=$i+$minimalSequenceSize; $j<$len; $j++) { 
     if ($input[$offset] == $input[$j]) { 
      $sequenceSize = 1; 
      $sequence = array($input[$offset]); 
      while (($offset + $sequenceSize < $j) 
       && ($input[$offset+$sequenceSize] == $input[$j+$sequenceSize])) { 

       if (false !== ($seqIndex = array_search($sequence, $frequences))) { 
        // we already have this sequence, since we found a bigger one, remove the old one 
        array_splice($sequences, $seqIndex, 1); 
        array_splice($frequences, $seqIndex, 1); 
       }    

       $sequence[] = $input[$offset+$sequenceSize]; 
       $sequenceSize++; 
      } 

      if ($sequenceSize >= $minimalSequenceSize) { 
       if (false !== ($seqIndex = array_search($sequence, $sequences))) { 
        $frequences[$seqIndex]++; 
       } else { 
        $sequences[] = $sequence; 
        $frequences[] = 2; // we have two occurances already 
       } 
       // $i += $sequenceSize; // move $i so we don't reuse the same sub-sequence 
       break; 
      } 
     } 
     } 
    } 

    // remove sequences that are sub-sequence of another frequence 
    // ** comment this to keep all sequences regardless ** 
    $len = count($sequences); 
    for ($i=0; $i<$len; $i++) { 
     $freq_i = $sequences[$i]; 
     for ($j=$i+1; $j<$len; $j++) { 
     $freq_j = $sequences[$j]; 
     $freq_inter = array_intersect($freq_i, $freq_j); 
     if (count($freq_inter) != 0) { 
      $len--; 
      if (count($freq_i) > count($freq_j)) { 
       array_splice($sequences, $j, 1); 
       array_splice($frequences, $j, 1); 
       $j--; 
      } else { 
       array_splice($sequences, $i, 1); 
       array_splice($frequences, $i, 1); 
       $i--; 
       break; 
      } 
     } 
     } 
    } 

    return array($sequences, $frequences); 
}; 

測試用例

header('Content-type: text/plain'); 

$input = array(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 3, 5, 65, 4, 7, 13, 32, 5, 48, 4, 7, 13); 

list($sequences, $frequences) = getFrequences($input); 
foreach ($sequences as $i => $s) { 
    echo "(" . implode(',', $s) . ') f=' . $frequences[$i] . "\n"; 
} 

** 編輯 **：這裏是一個更新的功能。它幾乎完全重寫了......告訴我這是不是你想要的。我還添加了冗餘檢查，以防止對相同的序列或子序列進行兩次計數。

function getFrequences2($input, $minSequenceSize = 2) { 
    $sequences = array(); 

    $last_offset = 0; 
    $last_offset_len = 0; 

    $len = count($input); 
    for ($i=0; $i<$len; $i++) { 
    for ($j=$i+$minSequenceSize; $j<$len; $j++) { 
     if ($input[$i] == $input[$j]) { 
      $offset = 1; 
      $sub = array($input[$i]); 
      while ($i + $offset < $j && $j + $offset < $len) { 
       if ($input[$i + $offset] == $input[$j + $offset]) { 
       array_push($sub, $input[$i + $offset]); 
       } else { 
       break; 
       } 
       $offset++; 
      } 

      $sub_len = count($sub); 
      if ($sub_len >= $minSequenceSize) { 
       // $sub must contain more elements than the last sequence found 
       // otherwise we will count the same sequence twice 
       if ($last_offset + $last_offset_len >= $i + $sub_len) { 
       // we already saw this sequence... ignore 
       continue; 
       } else { 
       // save offset and sub_len for future check 
       $last_offset = $i; 
       $last_offset_len = $sub_len; 
       } 

       foreach ($sequences as & $sequence) { 
       $sequence_len = count($sequence['values']); 
       if ($sequence_len == $sub_len && $sequence['values'] == $sub) { 
        //echo "Found add-full ".var_export($sub, true)." at $i and $j...\n"; 
        $sequence['frequence']++; 
        break 2; 
       } else { 
        if ($sequence_len > $sub_len) { 
         $end = $sequence_len - $sub_len; 
         $values = $sequence['values']; 
         $slice_len = $sub_len; 
         $test = $sub; 
        } else { 
         $end = $sub_len - $sequence_len; 
         $values = $sub; 
         $slice_len = $sequence_len; 
         $test = $sequence['values']; 
        } 
        for ($k=0; $k<=$end; $k++) { 
         if (array_slice($values, $k, $slice_len) == $test) { 
          //echo "Found add-part ".implode(',',$sub)." which is part of ".implode(',',$values)." at $i and $j...\n"; 
          $sequence['values'] = $values; 
          $sequence['frequence']++; 
          break 3; 
         } 
        } 
       } 
       } 

       //echo "Found new ".implode(',',$sub)." at $i and $j...\n"; 
       array_push($sequences, array('values' => $sub, 'frequence' => 2)); 
       break; 
      } 
     } 
    } 
    } 

    return $sequences; 
}; 

Answer 2

在Python3

>>> from collections import Counter 
>>> count_hash=Counter() 
>>> T=(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32) 
>>> for i in range(2,len(T)+1): 
...  for j in range(len(T)+1-i): 
...   count_hash[T[j:j+i]]+=1 
... 
>>> for k,v in count_hash.items(): 
...  if v >= 2: 
...   print(k,v) 
... 
(3, 5) 2 
(4, 7, 13) 2 
(7, 13) 2 
(4, 7) 2 

你需要過濾（7,13）和（4,7）嗎？如果序列中還有（99,7,14），會發生什麼？

一個Counter就像一個散列用於跟蹤我們看到每個子
兩個嵌套的for循環產生的T所有子的次數，使用count_hash積累每串的數量。
最後的環路濾波器所有那些只出現過一次

下面子是帶有過濾器的版本

from collections import Counter 
def substrings(t, minlen=2): 
    tlen = len(t) 
    return (t[j:j+i] for i in range(minlen, tlen+1) for j in range(tlen+1-i)) 

def get_freq(*t): 
    counter = Counter(substrings(t)) 
    for k in sorted(counter, key=len): 
     v=counter[k] 
     if v < 2: 
      del counter[k] 
      continue 
     for t in substrings(k): 
      if t in counter: 
       if t==k: 
        continue 
       counter[k]+=counter[t]-v 
       del counter[t] 
    return counter 

print(get_freq(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32, 4, 7)) 
print(get_freq(1,2,3,4,1,2,3,4,1,2,7,8,7,8,3,4,3,4,1,2)) 

輸出

Counter({(4, 7, 13): 3, (3, 5): 2}) 
Counter({(1, 2, 3, 4, 1, 2): 8, (7, 8): 2}) # Is this the right answer? 

這就是爲什麼我問怎麼過濾應該適用於我在評論中給出的順序

Answer 3

好吧，剛開始討論。

1. 創建另一個數組/地圖，稱這個權重數組爲 。
2. 開始迭代值數組。
3. 對於 values數組中的每個數值，在權重 數組中增加 對應的位置。例如：對於3增加 權重[3] ++，對於48 權重[48] ++。
4. 迭代後的權重數組包含 重複