Описание тега bk-tree
BK-дерево - это метрическое дерево, специально адаптированное для дискретных метрических пространств.
1
ответ
Как мне сбалансировать BK-дерево и нужно ли это?
Я пытаюсь использовать алгоритм Edit Distance для реализации нечеткого поиска в базе данных имен. Я нашел структуру данных, которая предположительно поможет ускорить это с помощью подхода "разделяй и властвуй" - деревья Беркхарда-Келлера. Проблема в…
31 дек '12 в 11:10
1
ответ
Как оптимизировать BK-Tree
Я реализую BK-дерево в Cython. Для одного миллиона предметов время поиска слишком велико! Это ~30 секунд:( Вот мой код Cython: # -*- coding: UTF-8 -*- from itertools import imap from PIL import Image DEF MAX_TREE_POOL = 10000 cdef extern from "dista…
07 апр '12 в 05:39
0
ответов
БК-дерево сложность
Для школы нам нужно было создать BK-дерево с функциями insert() и get(). Функция get() допускает, что max_distance будет только 1, поэтому к результатам будут добавлены только результаты в пределах расстояния 1 (LD-distance). Теперь нам нужно рассчи…
10 май '18 в 19:41
1
ответ
Правильно ли реализован этот алгоритм?
В настоящее время я использую BK-Tree для проверки орфографии. Словарь, с которым я работаю, очень большой (миллионы слов), поэтому я не могу позволить себе никакой неэффективности. Однако я знаю, что написанная мной функция поиска (возможно, самая …
05 окт '10 в 16:30
3
ответа
Понимание BK Trees: как мы получаем диапазон (dn, d+n) из неравенства треугольника?
Читая этот пост о BK Trees, я нашел следующий фрагмент немного запутанным: "Предположим на мгновение, что у нас есть два параметра: запрос, строка, которую мы используем в нашем поиске, и n максимальное расстояние, на которое строка может быть от за…
17 янв '16 в 19:42
1
ответ
Поиск друга в словаре с использованием расстояния Левенштейна
Вот что я пытаюсь сделать. Два слова W1 а также W2 друзья, если Levenshtein distance для этих слов 1. Я должен также найти всех друзей друга. Я пытался сделать то же самое с Bk-Tree. Он работает для словаря малого размера (словарь содержит только од…
16 июн '11 в 12:43
1
ответ
BK - Tree Search All
A BK Trees (деревья Буркхарда-Келлера) связаны с поиском нечетких строк (например, проверка орфографии, рекомендации по словам). И все алгоритмы поиска BK Trees соответствуют описанным здесь. Цель - вернуть, например, "seek" и "peek", если я ищу "ae…
26 авг '17 в 21:39
1
ответ
BK-Tree реализации Время вставки больше, как уменьшить
Следующее - моя попытка написать BK-Tree, для 150000 файл слова это занимает около 8 seconds Есть ли способ сократить это время. Ниже мой код #include <stdio.h> #include <string> #include <vector> #include <fstream> #include …
26 май '11 в 12:15
3
ответа
Как реализовать быструю нечеткую поисковую систему с использованием BK-дерева, когда в корпусе содержится 10 миллиардов уникальных последовательностей ДНК?
Я пытаюсь использовать структуру данных BK-tree в python для хранения корпуса с ~10 миллиардами записей ( 1e10) для реализации быстрой нечеткой поисковой системы. Как только я добавлю более ~10 миллионов ( 1e7) значений в одно BK-дерево, я начинаю з…
06 янв '21 в 03:15
0
ответов
Unmarshal [] байт в рекурсивную структуру с полем пользовательского интерфейса типа в Golang
type Node struct { Entry Entry `json:"e"` Children []child `json:"c"` } type child struct { Distance int `json:"d"` Node *Node `json:"n"` } type Entry interface { Distance(Entry) int json.Marshaler json.Unmarshaler } Как показано выше, у меня есть …
09 ноя '21 в 07:40