Как найти наиболее похожий битовый вектор в префиксном дереве для NN-поиска?

Question

Проблема, которую я пытаюсь решить, объясняется в этом вопросе: Найти единственного ближайшего соседа, используя дерево префиксов в O(1)?

Мой вопрос касается раздела " Предлагаемое решение " на этой странице вопросов. В этом разделе упоминается, что мы находим ближайшего соседа из каждого дерева префиксов, обходя дерево, начиная с узла. Хорошо посмотреть, существует ли ключ в дереве префиксов, просто, но получить самый похожий, которого я совсем не понимаю. Как это сделать?

Я хотел бы, если кто-то может объяснить это мне, если не графически (что является предпочтительным), то хотя бы с некоторыми деталями.

Редактировать:

вот код бумаги. Он написан на python, и, к сожалению, я никогда раньше не работал с python. Если кто-то знаком с Python и может найти код, чтобы увидеть, как они находят ближайших соседей, используя префиксные деревья. https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

Answer 1

Сначала узнайте, что они перебирают все дерево. Итерируя по всему дереву, они гарантированно находят наиболее похожих соседей.

Для большей эффективности в среднем случае используйте обход дерева DFS для дерева. Обратите внимание, что, поскольку это дерево, не будет необходимости в схеме раскраски для посещаемых узлов.

Начните с ближайшего объекта с нуля и с корня дерева.

Для каждого узла вы должны перемещать дочерние элементы в порядке их добавления к расстоянию редактирования и только в том случае, если добавленное расстояние редактирования не будет больше расстояния до ближайшего объекта. Например, с расстоянием Хэмминга сначала пройдитесь по дочернему элементу, который добавит "O" к общему расстоянию, а затем пройдитесь по дочернему элементу, который добавит "1" к общему расстоянию. Но не переходите к дочернему элементу "1", если это сделает расстояние редактирования больше текущего ближайшего расстояния.

Когда вы встретите "слово" в дереве префиксов, проверьте, имеет ли оно расстояние до объекта запроса меньше, чем ближайший объект, и назначьте его ближайшему.