Как отсортировать 32-битные числа, чтобы найти уникальные записи?

Question

Существует набор данных «file» - имя файла, за ним следует 32-битное число - что-то вроде хеша для файла.

"file1" 6a9bd9a6 1df3b24b 7ab054dc
"file2" 6a9bd54e 1df3b24b 8cd054dc
"file3" 6a9bd9a6 7ab054dc

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

Я ищу быстрое решение. Я мог бы предложить решение для сравнения каждой строки друг с другом, но это было бы слишком много времени и неэффективно. Другим вариантом было как-то использовать движок MySQL для таблиц, но я не уверен как. Вы можете помочь?

Answer 1

Вы можете использовать trie , чтобы убедиться, что ни одна строка не является префиксом любой другой строки.

Когда вы вставляете в свой файл, вы проверяете оба этих случая:

1) Я прошел старый листовой узел? Если это так, это означает, что другая строка является префиксом моей строки.
2) Хочу ли я отметить уже существующий не лист как лист? Если это так, я префикс другой строки.

Это будет решение O (N), где N - количество строк (измерение количества вставок в три). Каждая вставка выполняется для длины своей строки.

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