Сравнение двух попыток TRIE - PullRequest
0 голосов
/ 15 декабря 2018

Кто-нибудь знает алгоритм, который может сравнивать два дерева Trie и придумывать, какие элементы из одного Trie соответствуют тем элементам из другого Trie?

Пример:

  • I10 миллионов полустатических правил (изменяются один раз в день)
  • и 100 000 динамических элементов (изменение при каждом запуске)
  • каждое правило /Элемент имеет 99 строковых / числовых полей, которые необходимо сравнить
  • 80 из этих полей может иметь ограниченный набор значений от 1 до 1k (например: сравнить: рост против высоты; диапазон: возраст против мин / макс возраст; regex: имя начинается с и т. д.)

Мне нужно знать, какие элементы соответствуют какому из правил, и мне нужно запускать это столько раз в секунду, сколько возможно.

  • С простой грубой силой я получу 1x10 ^ 12 проверок.
  • Поскольку каждый столбец в моих наборах данных имеет ограниченное количество значений, если я строю три, я получаю 9,9 * 10 ^ 6 проверок длясоответствовать всем правилам, наихудший сценарий (99 столбцов * 100 тыс. элементов)
  • Но если бы я сравниля получаю что-то вроде 99x10 ^ 3 проверок (1k значений * 99 столбцов)

Кто-нибудь знает имя алгоритма, который сравнивает две попытки?

...