最快的搜索算法开始

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毫秒（给定或取消）暂停之前，您可能不应尝试点击字符串列表。第三，你对浩瀚的疑问应该是异步的和可取消的，因为它肯定会是下一次击键将取代一个努力的情况。

最后，任何后续查询应先检查新的搜索字符串是最近的搜索字符串的追加......这样你就可以开始你的后面从上觅觅（节省大量的时间）。