Самый быстрый способ поиска с рисунком

Question

Представьте, у меня есть список из нескольких сотен уникальных имен, например.

["john", "maria", "joseph", "richard", "samantha", "isaac", ...] 

Каков наилучший способ сохранить их, чтобы обеспечить быстрый поиск времени путем сопоставления с шаблоном?

Мне нужно только соответствовать «маскам», не могу придумать лучшего слова для этого.

В принципе, я получаю буквы и их позиции, ____a__ (где _ представляет собой неизвестную букву.) Затем мне нужно найти все значения в структуре данных, которые соответствуют этой маске, например. в этом случае он будет возвращать «richard», но также должно быть возможно получить несколько «возвращенных» значений.

Answer 1

Кажется, что много работы на «сотню» имен. Выполнение линейного поиска в списке сотен имен будет очень быстрым. Теперь, если вы говорите сотни тысяч или миллионы ...

В любом случае вы можете ускорить это, используя словарь. Вы можете предварительно обработать данные в словаре, ключи которого представляют собой комбинацию символа и положения, а значения - это слова, которые содержат этот символ в этой позиции. Например, если бы вы были индексом «сортир» и «Иосифом», вы бы:

{'j',0},{"john","jospeh"} 
{'o',1},{"john","joseph"} 
{'h',2},{"john"} 
{'n',3},{"john} 
{'s',2},{"joseph"} 
{'e',3},{"joseph"} 
{'p',4},{"joseph"} 
{'h',5},{"joseph"} 

Теперь предположим, что вы дали маску «джо ....» (точки являются «Дон» t care "). Вы бы превратить это в двух ключах:

{'j',0} 
{'o',1} 

Вы запросить словарь для списка слов, который имеет «J» с индексом 0. Тогда вы запрашиваете словарь для списка слов, которые есть «о» в index 1. Затем вы пересекаете списки, чтобы получить результат.

Это простой инвертированный указатель, но скорее на символ, чем на слово.

Списки сами будут стоить вам всего O (m * n) пространства, где m - общее количество слов, а n - средняя длина слова в символах.Максимально количество записей в словаре будет 26 * max_word_length. На практике это, вероятно, будет намного меньше.

Если вы делаете значения a HashSet<string>, а не List<string>, пересечение будет проходить намного быстрее. Тем не менее, это увеличит объем памяти.

Это должно быть быстрее линейного поиска, если ваши маски содержат только несколько символов. Чем дольше маска, тем больше списков вам придется пересекать.

Для словаря ключ, я бы рекомендовал:

public struct Key 
{ 
    public char KeyChar; 
    public int Pos; 
    public override int GetHashCode() 
    { 
     return (int)KeyChar + Pos << 16; 
    } 
    public override bool Equals(object obj) 
    { 
     if (!obj is Key) return false; 
     var other = (Key)obj; 
     return KeyChar == other.KeyChar && Pos == other.Pos; 
    } 
} 

Так ваш словарь будет Dictionary<Key, HashSet<string>>.

Answer 2

Если длинное слово имеет m букв, то вы можете сохранить m списков l [1], ..., l [m] так, чтобы слова в каждом списке l [i] были отсортированы лексикографически, начиная с i- го письма в каждом слове (более короткие слова не будут отображаться в этом списке). Затем, если ваш запрос равен ...ac., просто выполните двоичный поиск в списке l [4].

Это будет стоить вам O (mn) в памяти и займет время O (m n log n) для создания, но даст вам время запроса O (log n), которое является самым быстрым, которое вы можете получить.

EDIT
Хорошие новости, я недавно наткнулся на range trees, что позволит вам несколько эффективно выполнять такого рода запросов, а именно в O (журнал^т (п) + к) времени, и требующих вывода (n log^(d-1) (n)).

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

С другой стороны, это позволит выполнять более широкий спектр запросов, а именно вы можете искать смежные интервалы букв, т.е. шаблона, как ..[a-c].[b-f].