структура данных для поддержки поиска на основе полного ключа или части ключа

Question

Мне нужно иметь возможность поиска по полному ключу или его части.

Например, я могу хранить ключи, такие как 10,20,30,40 11,12,30,40, 12, 20,30,40

Я хочу иметь возможность искать 10,20,30,40 или 20,30,40

Какая структура данных наилучшая для достижения этой цели ..Лучшее время.

наш язык программирования - Java. Будем признательны за любые указатели для проектов с открытым исходным кодом.

Заранее спасибо ..

Answer 1

Если бы это были настоящие числа, с которыми я бы работал, я бы использовал массив, в котором заданный индекс содержит массив всех записей, которые содержат индекс. Если бы действительные числа были больше, я бы использовал хеш-таблицу, использованную таким же образом.

Таким образом, структура будет выглядеть (пустые индексы исключены в случае реализации массива):

10 => ((10,20,30,40)),
11 => ((11,12,30,40)),
12 => ((11,12,30,40), (12,20,30,40)),
20 => ((10,20,30,40), (12,20,30,40)),
30 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),
40 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),

Мне не ясно, являются ли ваши поиски инклюзивным (на основе ИЛИ) или эксклюзивным (на основе И), но в любом случае вы ищите группы записей для каждого элемента поискового набора; для инклюзивного поиска вы найдете их объединение, а для эксклюзивного поиска вы найдете их пересечение.

Answer 2

Используйте древовидную структуру. Вот проект с открытым исходным кодом, который может помочь ... написанный на Java: -)
http://suggesttree.sourceforge.net/

Answer 3

Поскольку вы заботитесь о времени поиска по сравнению с другими проблемами (такими как пространство), я предлагаю вам использовать хеш-таблицу и вводить свои элементы несколько раз, по одному на каждый подраздел. Таким образом, вы должны поставить («10,20,30,40», mydata), затем поставить («20,30,40», mydata) и так далее (конечно, это будет метод, вы не собираетесь вручную звонил ставить так много раз).