Обнаружение изменений в случайном упорядоченном входе (хэш-функция?)

Question

Я читаю строки текста, которые могут прийти в любом порядке. Проблема в том, что результат может быть фактически идентичен предыдущему. Как я могу обнаружить это, не сортируя вывод в первую очередь?

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

Answer 1

Казалось бы, самый простой способ - хешировать каждую строку в пути, хранить хеш и исходные данные, а затем сравнивать каждый новый хеш с вашей коллекцией существующих хешей. Если вы получили положительный результат, вы можете сравнить фактические данные, чтобы убедиться, что это не ложный положительный результат - хотя это будет крайне редко, вы можете использовать более быстрый алгоритм хеширования, такой как MD5 или CRC (вместо чего-то вроде SHA, который медленнее, но с меньшей вероятностью столкновения), просто так быстро, а затем сравните фактические данные, когда вы получите удар.

Answer 2

Ну, спецификация проблемы немного ограничена.

Насколько я понимаю, вы хотите увидеть, содержат ли несколько строк одинаковые элементы независимо от порядка.

Например:

A B C
C B A

одинаковы.

Способ сделать это - создать набор значений, а затем сравнить наборы. Для создания набора выполните:

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

Затем просто сравните содержимое наборов, пропустив один из наборов и сравнив его с другими. Время выполнения будет O(N) вместо O(NlogN) для примера сортировки.

Answer 3

Любой из основанных на хэше методов может давать плохие результаты, потому что более одной строки могут создавать один и тот же хеш. (Это маловероятно, но возможно.) Это особенно верно в отношении предложения добавить хэши, поскольку вы, по сути, взяли бы особенно плохой хеш значений хеш-функции.

Хеш-метод следует использовать только в том случае, если не важно, чтобы вы пропустили изменение или обнаружили изменение там, где его нет.

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

• Если вы столкнулись с линией с нулевым счетом (или вообще без записи на карте), вы увидели линию, которую вы не ожидали.
• Если вы закончите с ненулевыми записями, оставшимися на карте, вы не увидите того, чего ожидали.

Answer 4

Если вы сложите значения ASCII для каждого символа, вы получите один и тот же результат независимо от порядка.

(Это может быть слишком упрощенно, но, возможно, это вызывает у вас идею. См. Программирование Жемчуг, раздел 2.8, для интересной истории.)

Answer 5

Если строки довольно длинные, вы можете просто сохранить список хэшей каждой строки - отсортировать их и сравнить с предыдущими выходными данными.

Если вам не нужно 100% надежное решение, вы можете сохранить хэш каждой строки в фильтре Блума (посмотрите в Википедии) и сравнить фильтры Блума в конце обработки. Это может дать вам ложные срабатывания (то есть вы думаете, что у вас есть тот же вывод, но на самом деле это не то же самое), но вы можете настроить частоту ошибок, отрегулировав размер фильтра Блума ...

Answer 6

Если вы хотите выяснить, содержат ли два файла одинаковый набор строк, но в другом порядке, вы можете использовать обычную хеш-функцию для каждой строки отдельно, а затем объединить их с функцией, где порядок не имеет значения как дополнение.

Answer 7

Таким образом, у вас есть ввод, как

A B C D
D E F G
C B A D

а вам нужно обнаружить, что первая и третья строки идентичны?