как найти ближайшую сигнатуру в битовом массиве по битовому массиву?

учитывая Trie битов и вход в виде битового массива/вектора, как я могу найти ближайшего соседа для входного вектора в Trie?

Алгоритм, который я пытаюсь сделать, следующий: учитывая битовый вектор V и функцию перестановки F, сделайте следующее:

1- F(V) = V_; где V_ — подпись V.

2- Вставьте V_ в тройку;

через некоторое время... задан битовый вектор U, делаем следующее:

1- F(U) = U_;

2- Найдите ближайшую подпись в дереве.

Ближайшая сигнатура определяется расстоянием Хэмминга.


java algorithm tree trie
person Jack Twain    schedule 19.06.2013    source источник
comment
Как вы определяете ближайшего соседа?   -  person templatetypedef    schedule 20.06.2013
comment
@templatetypedef Ближайшая подпись определяется расстоянием Хэмминга.   -  person Jack Twain    schedule 20.06.2013
comment
Вы должны использовать попытку здесь? Для этого есть гораздо лучшие структуры данных.   -  person templatetypedef    schedule 20.06.2013
comment
@templatetypedef да, я читаю статью и пытаюсь понять, почему они делают шаг, для этого мне нужно это понять.   -  person Jack Twain    schedule 20.06.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

person Markus Jarderot    schedule 19.06.2013