Нахождение частой последовательности чисел в массиве
Массив (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) , чтобы было понятно, рассмотрите каждое число как слово, и вы хотите найти наиболее часто встречающиеся фразы
, чтобы часто можно было встретить одно и то же слово (а) во множестве фраз, но если какая-либо фраза была подстрокой для любой другой
фразы (ей), не следует рассматривать как фразу, но будет обновляться частота каждой фразы, включающей ее
3 ответа
** РЕДАКТИРОВАТЬ **: немного лучшая реализация, теперь также возвращает частоты и имеет лучший фильтр последовательности.
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;
};
Хорошо, просто чтобы начать обсуждение.
- Создайте еще один массив / карту, назовите это массив весов.
- Начать итерацию по массиву значений.
- Для каждого значения в массив значений, увеличиваем соответствующее положение по весу множество. Например: на 3 прибавки вес [3] ++, для 48 вес [48] ++.
- После итерации массив весов содержит повторы
В 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)?
a Счетчик - это просто хэш, используемый для отслеживания количества просмотров каждой подстроки
.
Два вложенных цикла for создают все подстроки T, используя count_hash для накопления счета каждой подстроки.
Последний цикл for фильтрует все те подстроки, которые встречаются только один раз
Вот версия с фильтром
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?
Именно поэтому я спросил, как должна работать фильтрация для последовательности, которую я привел в комментариях