Какая структура данных самая быстрая, чтобы найти наиболее подходящий префикс?
Контекст: я работаю над анализатором для строк useragent ( Yauaa), и в рамках этого анализа я хочу сделать обоснованное предположение, о какой марке устройства следует сообщать. У меня есть реализация, которую мне нужно переписать, чтобы она была намного более эффективной.
Поскольку я не хочу иметь полный список всех устройств, я хочу выполнить обнаружение на основе префикса модели.
Итак, у меня есть набор данных с префиксами и брендом, который связан:
- "GT-" ->"Самсунг"
- "LLD-" -> "Huawei"
И затем я хочу сделать.get("GT-1234124"), который должен привести к "Samsung", потому что это "самый длинный префикс соответствия".
Я взглянул на структуру Trie, но, похоже, это противоположная ситуация. Насколько я понимаю, вы начинаете с набора значений и можете эффективно получить все значения, которые начинаются с указанного префикса.
Если бы я реализовал это с нуля, я бы использовал дерево, похожее на Trie, но обходил бы его по-другому. То, что я ищу, - это структура данных, которая делает то, что мне нужно, как можно быстрее.
Какую структуру данных вы рекомендуете для этого варианта использования?
Есть ли существующая (проверенная) реализация, которую я могу использовать?
1 ответ
Я немного покопался в структурах данных и обнаружил, что по сути структура Trie - это то, что мне нужно, с другим способом обхода структуры.
Поскольку эта структура действительно проста, я создал свою собственную реализацию, которая работает очень хорошо.