Реализация поиска в стиле графов
Хочу сделать реализацию поиска совпадений в стиле графов или ещё как-то. Есть много 16 байтовых строк, чтобы не проверять простым for хочу искать последовательно вглубь графа. Т.е. я это вижу приблизительно так, каждая нода содержит массив где ключ ссылается на другой массив. Первый байт помещаем в первый слой и делаем ммылку на следущий слой, где второй байт становится ключём. Грубо говоря это как многомерный массив где первый байт это первый уровень, и он ссылается на вложенный массив где лежат вторые байты и строк. В принципе есть два больших набора байтовых массивов фиксированной длинны, т.е. каждый элемент массива имеет одинаковый размер. Нужно искать совпадения, подскажите куда копать?
Ответы (1 шт):
Проще всего организовать set - в golang - на основе map из данных первого набора, и потом проверять значения из второго набора на наличие в этом множестве.
Хотя элементы данных не такие уж длинные, но всё-таки каждый 16-байтный массив второго набора будет обрабатываться полностью для вычисления хэша.
Поэтому стоит проверить и вашу идею про проверку первого байта, потом второго и т.д. Одна из лучших структур данных для этого - trie.
Несовпадающие байты в большинстве своём будут отсекаться на ранней стадии, поэтому проверки должны быть довольно быстрыми. Вот произвольно взятая ссылка на реализацию trie на golang (выглядит не очень серьезно, но как отправная точка - подойдёт)