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

Что я пробовал

Наш учитель потребовал, чтобы мы протестировали различные решения и посмотрели, что мы можем придумать. Первое очевидное решение — просмотреть списки телефонных номеров и их стоимости и посмотреть, что мы можем найти. Это потребовало бы O (n) времени, если бы не было совпадений. Это решение становится еще хуже, поскольку мы также рассматриваем проблему с сохранением префиксов. Если бы не было совпадения для +14151234567, то как наша программа узнала бы, что нужно найти +1415? Первоначально я рассматривал возможность усечения последней цифры, а затем повторного поиска в списке, но это потенциально потребовало бы прохождения большого списка чисел до 11 раз.

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

Затем я попытался

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

Это пример compact trie или radix-дерева. Принцип работы trie заключается в том, что дочерние элементы с общими префиксами будут иметь одного и того же родителя. В этом примере все слова начинаются с буквы r, поэтому родителем/предком всех узлов будет r. Если бы к этому слову было добавлено слово резина, оно было бы в r, а затем переходило бы прямо в ub. Остальные буквы не имеют общего префикса с путем e или ic, поэтому необходимо создать новый.

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

Десятичное дерево поиска

Я решил создать trie, предназначенный для использования только с цифрами (в базе 10) для моего решения. Принцип работы прост.

Каждый узел имеет 10 дочерних элементов, хранящихся в массиве с индексами от 0 до 9. Чтобы найти данные для заданного числа, скажем, +1415, мы должны начать с корня, всегда являющегося знаком «+». Затем мы усекаем первую цифру «1» и переходим к этому индексу. Повторите этот процесс, чтобы корень -> индекс 1 -> индекс 4 -> индекс 1 -> индекс 5.

Итак, в чем преимущество использования trie по сравнению с другой структурой? Другой структурой данных, обычно используемой для поиска, является хеш-таблица. Хотя в хеш-таблице время поиска почти постоянно, ей требуется много памяти в одном и том же месте, чтобы оставаться таким быстрым. В тестах для этой задачи мне дали 10 миллионов чисел для поиска. Чтобы обеспечить достойную производительность при коэффициенте загрузки 0,75 или меньше, потребуется хеш-таблица с как минимум чуть более 13,3 миллиона сегментов. При тестировании моего дерева оно обычно содержало чуть более 4,8 миллиона узлов, из которых около 75% содержали данные о фактических затратах, а не являлись узлами обхода. Хотя это зависит от точных данных, компактное дерево может еще больше сократить количество узлов. В этом случае из-за большого количества совпадений в протестированных телефонных номерах (обычно начинающихся с +1415 и нескольких других кодов городов США) это было не столь существенно, но все же является оптимизацией.