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

Question

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

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

Answer 1

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

Answer 2

Итак, у вас есть входные данные, подобные

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

(Возможно, это немного упрощено, но, возможно, это подскажет вам идею.Интересную предысторию смотрите в разделе 2.8 "Жемчужины программирования".)

Answer 6

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

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

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

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

Answer 7

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

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

Например:

A B C
C B A

являются одними и теми же.

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

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

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