Какая структура данных C # позволяет наиболее эффективно искать подстроки в паре строк?

Question

У меня есть структура данных, которая состоит из пар значений, первое из которых является целым числом, а второе - буквенно-цифровой строкой (которая может начинаться с цифр):

+--------+-----------------+
| Number | Name            |
+--------+-----------------+
| 15     | APPLES          |
| 16     | APPLE COMPUTER  |
| 17     | ORANGE          |
| 21     | TWENTY-1        |
| 291    | 156TH ELEMENT   |
+--------+-----------------+

Таблицаиз них будет составлять до 100 000 строк.

Я хотел бы предоставить функцию поиска, в которой пользователь может искать либо число (как если бы это была строка), либо фрагменты строки.В идеале поиск будет "живым", когда пользователь вводит текст;после каждого нажатия клавиши (или, возможно, после небольшой задержки ~ 250-500 мс) будет выполняться новый поиск, чтобы найти наиболее вероятных кандидатов.Так, например, поиск по

• 1 вернет 15 APPLES, 16 APPLE COMPUTER, 17 ORANGE, а 291 156TH ELEMENT
• 15 сузит поиск до15 APPLES, 291 156TH ELEMENT
• AP вернет 15 APPLES и 16 APPLE COMPUTER
• (в идеале, но не обязательно) ELEM вернет 291 156TH ELEMENT.

Я думал об использовании двух Dictionary<string, string> с, поскольку в конечном итоге int сравниваются как string с - один будет индексироваться целой частью, а другой - строкой.

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

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

В противном случае, как насчет SortedDictionary?Может повысить производительность, но все равно не решит проблему с хешем.

Мысль о создании регулярного выражения на лету, но я думаю, что это будет работать ужасно.

Я новичок в C # (пришедший из мира Java), поэтому я еще не изучал LINQ;это ответ?

РЕДАКТИРОВАТЬ 18:21 EST : ни одна из строк в поле «Имя» не будет длиннее 12-15 символов, если это влияет на ваше потенциальное решение.

Answer 1

Если возможно, я бы не стал загружать все 100 000 записей в память. Я бы использовал базу данных или Lucene.Net для индексации значений. Затем используйте соответствующий синтаксис запроса для эффективного поиска результатов.

Answer 2

Я бы подумал об использовании Trie структуры данных.

Как этого добиться?Листья будут представлять вашу «строку», но у вас будет «два пути» к каждому экземпляру памяти «строки» (один для числа, а другой для имени).

Затем вы можете пожертвовать своим условием:

(ideally, but not required) ELEM will return 291 156TH ELEMENT.

Или укажите еще больше путей к экземплярам строк.

Answer 3

Поскольку вы ищете начало слов, коллекции на основе ключей не будут работать, если вы не сохраните все возможные фрагменты слов, такие как «a», «ap», «app», «appl», «apple» ,

Я предлагаю использовать System.Collections.Generic.List<T> в сочетании с бинарным поиском. Вы должны предоставить свой IComparer<T>, который также находит начало слов. Вы бы использовали две структуры данных.

Один List<KeyValuePair<string,int>>, содержащий отдельные слова или число в качестве ключа и число в качестве значения.

Один Dictionary<int,string>, содержащий все имя.

Вы бы поступили так:

1. Разделите ваше предложение (полное имя) на отдельные слова.

2. Добавьте их в список со словом в качестве ключа и числом в качестве значения KeyValuePair.

3. Добавить номер в список в качестве ключа и в качестве значения KeyValuePair.

4. Когда список заполнен, отсортируйте список, чтобы разрешить двоичный поиск.

Поиск начала слова:

1. Поиск в списке с помощью BinarySearch в сочетании с вашим IComparer<T>.

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

3. Используя номер, сохраненный в качестве значения в списке, найдите полное имя в словаре, используя этот номер в качестве ключа.