最快的搜索算法開始

Question

我需要實現一個搜索算法，它只能從字符串的開頭搜索，而不是在字符串中的任何位置。

我是新算法，但從我可以看到它看起來好像他們通過字符串，並找到任何發生。

我有一個字符串集合（超過100萬），需要搜索每次用戶鍵入按鍵。

編輯：

這將是一個漸進式搜索。我現在用下面的代碼實現了它，我的搜索範圍從100多萬個可能的字符串返回300-700ms之間。收集沒有訂購，但沒有理由不能。

private ICollection<string> SearchCities(string searchString) { 
     return _cityDataSource.AsParallel().Where(x => x.ToLower().StartsWith(searchString)).ToArray(); 
    } 

Answer 1

我修改了代碼this article from Visual Studio Magazine，它實現了Trie。

下面的程序演示如何使用Trie做快速前綴搜索。

爲了運行這個程序，你需要所謂的「words.txt」文字的大名單的文本文件。You can download one from Github here。

編譯完程序後，將「words.txt」文件複製到與可執行文件相同的文件夾中。

當您運行程序時，鍵入一個前綴（如prefix;））並按return，它會列出以該前綴開頭的所有單詞。

這應該是一個非常快速的查找 - 請參閱Visual Studio Magazine文章以獲取更多詳細信息！

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
using System.Text; 

namespace ConsoleApp1 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var trie = new Trie(); 
      trie.InsertRange(File.ReadLines("words.txt")); 

      Console.WriteLine("Type a prefix and press return."); 

      while (true) 
      { 
       string prefix = Console.ReadLine(); 

       if (string.IsNullOrEmpty(prefix)) 
        continue; 

       var node = trie.Prefix(prefix); 

       if (node.Depth == prefix.Length) 
       { 
        foreach (var suffix in suffixes(node)) 
         Console.WriteLine(prefix + suffix); 
       } 
       else 
       { 
        Console.WriteLine("Prefix not found."); 
       } 

       Console.WriteLine(); 
      } 
     } 

     static IEnumerable<string> suffixes(Node parent) 
     { 
      var sb = new StringBuilder(); 
      return suffixes(parent, sb).Select(suffix => suffix.TrimEnd('$')); 
     } 

     static IEnumerable<string> suffixes(Node parent, StringBuilder current) 
     { 
      if (parent.IsLeaf()) 
      { 
       yield return current.ToString(); 
      } 
      else 
      { 
       foreach (var child in parent.Children) 
       { 
        current.Append(child.Value); 

        foreach (var value in suffixes(child, current)) 
         yield return value; 

        --current.Length; 
       } 
      } 
     } 
    } 

    public class Node 
    { 
     public char Value { get; set; } 
     public List<Node> Children { get; set; } 
     public Node Parent { get; set; } 
     public int Depth { get; set; } 

     public Node(char value, int depth, Node parent) 
     { 
      Value = value; 
      Children = new List<Node>(); 
      Depth = depth; 
      Parent = parent; 
     } 

     public bool IsLeaf() 
     { 
      return Children.Count == 0; 
     } 

     public Node FindChildNode(char c) 
     { 
      return Children.FirstOrDefault(child => child.Value == c); 
     } 

     public void DeleteChildNode(char c) 
     { 
      for (var i = 0; i < Children.Count; i++) 
       if (Children[i].Value == c) 
        Children.RemoveAt(i); 
     } 
    } 

    public class Trie 
    { 
     readonly Node _root; 

     public Trie() 
     { 
      _root = new Node('^', 0, null); 
     } 

     public Node Prefix(string s) 
     { 
      var currentNode = _root; 
      var result = currentNode; 

      foreach (var c in s) 
      { 
       currentNode = currentNode.FindChildNode(c); 

       if (currentNode == null) 
        break; 

       result = currentNode; 
      } 

      return result; 
     } 

     public bool Search(string s) 
     { 
      var prefix = Prefix(s); 
      return prefix.Depth == s.Length && prefix.FindChildNode('$') != null; 
     } 

     public void InsertRange(IEnumerable<string> items) 
     { 
      foreach (string item in items) 
       Insert(item); 
     } 

     public void Insert(string s) 
     { 
      var commonPrefix = Prefix(s); 
      var current = commonPrefix; 

      for (var i = current.Depth; i < s.Length; i++) 
      { 
       var newNode = new Node(s[i], current.Depth + 1, current); 
       current.Children.Add(newNode); 
       current = newNode; 
      } 

      current.Children.Add(new Node('$', current.Depth + 1, current)); 
     } 

     public void Delete(string s) 
     { 
      if (!Search(s)) 
       return; 

      var node = Prefix(s).FindChildNode('$'); 

      while (node.IsLeaf()) 
      { 
       var parent = node.Parent; 
       parent.DeleteChildNode(node.Value); 
       node = parent; 
      } 
     } 
    } 
} 

Answer 2

我建議使用linq。

string x = "searchterm"; 
List<string> y = new List<string>(); 
List<string> Matches = y.Where(xo => xo.StartsWith(x)).ToList(); 

其中x是你的擊鍵搜索文本項，y爲你的字符串搜索的集合，比賽是從您的收藏比賽。

我與第一百萬素數測試這一點，這裏是改編自上面的代碼：

 Stopwatch SW = new Stopwatch(); 
     SW.Start(); 
     string x = "2"; 
     List<string> y = System.IO.File.ReadAllText("primes1.txt").Split(' ').ToList(); 
     y.RemoveAll(xo => xo == " " || xo == "" || xo == "\r\r\n"); 
     List <string> Matches = y.Where(xo => xo.StartsWith(x)).ToList(); 
     SW.Stop(); 
     Console.WriteLine("matches: " + Matches.Count); 
     Console.WriteLine("time taken: " + SW.Elapsed.TotalSeconds); 
     Console.Read(); 

結果是：

比賽：77025

拍攝時間：0.4240604

當然這是測試針對麻木我不知道linq之前是否轉換了數值，或者數字是否有所不同。

Answer 3

一對夫婦的想法：

首先，你千萬字符串需要訂購，這樣就可以「求」到第一個匹配的字符串，並返回一個字符串，直到你不再有比賽......爲了（可能通過C＃List<string>.BinarySearch查找）。這就是你觸摸儘可能少的字符串的方式。

其次，在輸入中至少有500毫秒（給定或取消）暫停之前，您可能不應嘗試點擊字符串列表。第三，你對浩瀚的疑問應該是異步的和可取消的，因爲它肯定會是下一次擊鍵將取代一個努力的情況。

最後，任何後續查詢應先檢查新的搜索字符串是最近的搜索字符串的追加......這樣你就可以開始你的後面從上覓覓（節省大量的時間）。