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

Question

Я хочу реализовать пошаговый поиск по списку строк. Представьте, что у меня есть массив, содержащий строки: store, state, stamp, crawl, crow. В моем приложении есть текстовое поле, в которое пользователь вводит строку поиска. Теперь, когда пользователь вводит текст, мне нужно выделить все совпадения. Например, когда пользователь вводит «st», мне нужно выделить «Store, state, stamp», теперь, когда он печатает «a», мне нужно удалить «Store» из списка. фреймворк. Что я планирую сделать, так это то, что в случае изменения текста я выполняю поиск в фоновом режиме и показываю результаты. Есть ли другой способ решить эту проблему?

Answer 1

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

Но что, если пользователь вставит несколько букв из буфера обмена, удалит несколько букв, выделив их, вставит или удалит одну или несколько букв где-то посередине?

Вам нужно следить за многими делами. Вы можете сделать метод с вновь введенной буквой и вернуться к полному повторному сканированию, если текст поиска изменился не так, как добавление одной буквы, но даже этот простой метод, вероятно, не стоит усилий, чтобы избежать нескольких десятков или сто строк сравнения. Как уже упоминалось, Trie или Patricia trie - это путь, если у вас действительно большие наборы данных или вы хотите быть очень быстрыми.

Answer 2

В прошлом мне приходилось делать что-то похожее, используя коллекцию, содержащую приблизительно 500 000 слов. Я обнаружил, что направленный ациклический граф слов работал хорошо. У DAWG примерно такая же производительность, как у дерева, но она будет более экономной. Однако его немного сложнее реализовать.

К сожалению, моя работа была на C, и у меня нет хороших ссылок для реализации DAWG на C #.

Answer 3

A три структуры данных будут хорошо масштабироваться, если ваш список может увеличиться до значительной длины (более сотни записей). Проверьте, например, этот пример реализации .

Answer 4

Ну, я реализовал Trie и DAWG для этой проблемы, и я наткнулся на 2 головы скребков:

1) DAWG -> Directed ACYCLIC Word Graph. Как вы создаете этот график / пересекаете его с такими словами, как «бот» и «boot», «oo» при загрузке вызовет цикл на основе DAWG 2) Trie устраняет эту проблему, но затем вводит некоторые проблемы управления филиалами.

Построить график намного проще (IMO), чем фактически использовать его для создания нужных слов без увеличения времени выполнения.

Я все еще работаю над этим.

Answer 5

Вау ...

Просто используйте встроенную функцию автозаполнения в текстовом поле. Вы можете предоставить ему свой список слов, и он подойдет для вас.

Answer 6

Вместо массива строк вы можете использовать общую коллекцию. Таким образом, вы можете использовать метод FindAll с делегатом для поиска по элементам.

string searchString = "s";
List<string> sl = new List<string>();
sl.Add("store");
sl.Add("state");
sl.Add("stamp");
sl.Add("crawl");
sl.Add("crow");
List<string> searchResults = sl.FindAll(delegate(string match) 
                                                { 
                                                    return   match.StartsWith(searchString, StringComparison.CurrentCultureIgnoreCase); 
                                                });

Answer 7

Ниже приведена функция, которая будет постепенно искать строку для поиска подстроки.

public IEnumerable<int> FindAllMatches(string toMatch, string source) {
  var last = 0;
  do {
    var cur = source.IndexOf(toMatch,last);
    if ( cur < 0 ) {
      break;
    }
    yield return cur;
    last = cur + toMatch.Length;
  while(true);
}