Подсчет общих байтов, слов и двойных слов

Question

Я сканирую большое количество данных и ищу общие тенденции в них. Каждый раз, когда я встречаю повторение единицы, я хочу увеличить ее счет. Какова лучшая структура данных или способ хранения этих данных. Мне нужно быстро найти его, а также подсчитать каждую единицу данных.

Answer 1

Вы не указали язык, но хеш (ассоциативный массив) - ваша лучшая структура данных.

Иногда его можно назвать картой / хэш-картой в зависимости от языка (в Java есть HashMaps, хеш-коды Perl,

Структура данных хэш / ассоциативный массив / карта состоит из набора пар ключ-значение, значения которых могут быть установлены / получены с помощью ключа. В вашем случае ключом будет строка, представляющая слово, байт или двойное слово (отдельные 3 хеш-карты), а значением будет счетчик частоты.

Answer 2

Как уже отмечали другие, хеш является очевидным кандидатом для вашей структуры данных.

Однако для целей разработки и тестирования я бы хотел, чтобы эта структура была богаче простого подсчета для каждого соответствующего элемента. Скорее, я бы хотел хранить информацию, которую можно было бы использовать для подтверждения правильности кода.

Для начала эта информация может содержать номер строки и некоторое указание позиции, где произошло совпадение. Вот иллюстрация в Perl:

use strict;
use warnings;

my %regexes= (
    rep_letter => qr/ ([a-z])         (\1   )+ /x,
    rep_word   => qr/ (\b \w+ \b) \W* (\1\W*)+ /x,
    doub_word  => qr/ (\b \w+   ) \W+  \1      /x,
);

my %ds;

while (my $line = <>){
    for my $r (keys %regexes){
        while ( $line =~ /$regexes{$r}/g ){
            # Data structure:
            #   $ds{REGEX_TYPE}{REPEATED_ITEM} = [
            #       [LINE_NO, pos_VALUE_OF_MATCH],
            #       etc. for each match
            #   ]
            #
            # For example:
            #   $ds{rep_word}{foo} = [
            #       [ 3, 11],
            #       [12, 88],
            #       ...
            #   ]
            push @{$ds{$r}{$1}}, [$., pos($line)];
        }
    }
}

Answer 3

Как уже упоминалось, словари / хеш-таблицы - ваш лучший выбор.Но ваш вопрос немного ясен, и я заметил, что вы упомянули сжатие в ваших тегах;Вы также можете посмотреть на деревья Хаффмана .

Answer 4

Словарь / Хеш-таблица была бы лучшей, если вам нужен быстрый поиск.