Кто-нибудь знает алгоритм, который может сравнивать два дерева Trie и придумывать, какие элементы из одного Trie соответствуют тем элементам из другого Trie?
Пример:
- I10 миллионов полустатических правил (изменяются один раз в день)
- и 100 000 динамических элементов (изменение при каждом запуске)
- каждое правило /Элемент имеет 99 строковых / числовых полей, которые необходимо сравнить
- 80 из этих полей может иметь ограниченный набор значений от 1 до 1k (например: сравнить: рост против высоты; диапазон: возраст против мин / макс возраст; regex: имя начинается с и т. д.)
Мне нужно знать, какие элементы соответствуют какому из правил, и мне нужно запускать это столько раз в секунду, сколько возможно.
- С простой грубой силой я получу 1x10 ^ 12 проверок.
- Поскольку каждый столбец в моих наборах данных имеет ограниченное количество значений, если я строю три, я получаю 9,9 * 10 ^ 6 проверок длясоответствовать всем правилам, наихудший сценарий (99 столбцов * 100 тыс. элементов)
- Но если бы я сравниля получаю что-то вроде 99x10 ^ 3 проверок (1k значений * 99 столбцов)
Кто-нибудь знает имя алгоритма, который сравнивает две попытки?