Tìm chuỗi thường xuyên các con số trong một mảng

Question

Mảng (3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32)

chuỗi thường xuyên các con số sẽ (3, 5) f=2 + (4, 7, 13) f=2

bất kỳ thuật toán hoặc giả mã để thấy rằng?

Cập nhật (1):

nếu (7, 13) cũng xảy ra nó sẽ được đưa vào một trong những lâu nhất bởi bản cập nhật tần số của nó để

(4, 7, 13) f=3 và vân vân ...

Update (2):

trong trường hợp (1,2,3,4,1,2,3,4,1,2,7,8,7,8,3,4,3,4,1,2) sản lượng nên được (1,2,3,4) & (3,4,1,2)

& (7,8), để làm cho nó rõ ràng xem xét mỗi số là một từ và bạn muốn tìm các cụm từ thường gặp nhất

nên rất phổ biến để xem cùng một từ (s) trong rất nhiều cụm từ nhưng nếu bất kỳ cụm từ là phụ -string cho bất kỳ khác

cụm từ (s) không nên được xem xét như một cụm từ nhưng sẽ cập nhật tần số của mỗi cụm từ bao gồm nó

Answer 1

** EDIT **: thực hiện tốt hơn một chút, bây giờ cũng trả frequences và có một bộ lọc tự tốt hơn.

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); 
}; 

Kiểm tra trường hợp

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"; 
} 

** EDIT **: đây là một bản cập nhật để hàm. Nó gần như được viết lại hoàn toàn ... cho tôi biết nếu đây là thứ bạn đang tìm kiếm. Tôi cũng đã thêm một kiểm tra dự phòng để ngăn đếm cùng một chuỗi, hoặc sau đó, hai lầ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

trong 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 

Bạn có cần lọc (7,13) và (4,7) không? Điều gì xảy ra nếu cũng có (99, 7, 14) trong chuỗi?

một Counter là giống như một băm được sử dụng để theo dõi số lần chúng ta thấy mỗi chuỗi
Hai lồng nhau cho vòng sản xuất tất cả các chuỗi con của T, sử dụng count_hash để tích lũy số lượng của mỗi chuỗi con.
Các thức cho các bộ lọc vòng lặp tất cả những chuỗi con mà chỉ xảy ra một lần

Đây là một phiên bản với một bộ lọc

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)) 

đầu ra là

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

Đó là lý do tại sao tôi hỏi cách lọc nên hoạt động cho chuỗi mà tôi đưa ra trong các nhận xét

Answer 3

Ok, chỉ để bắt đầu thảo luận.

1. Tạo một mảng/bản đồ khác, gọi đây là mảng trọng số.
2. Bắt đầu lặp lại trên mảng giá trị.
3. Đối với mỗi giá trị trong các mảng giá trị , tăng vị trí tương ứng trong trọng số mảng. Ví dụ: cho 3 tăng trọng số [3] ++, cho 48 trọng số [48] ++.
4. Sau khi lặp mảng weightage chứa lặp lại