你能在带有子字符串比较的字符串列表上运行二进制搜索吗?
本文关键字:字符串 运行 二进制 搜索 列表 比较 | 更新日期: 2023-09-27 17:49:26
问题是我有一个大约80万个字符串元素的列表,并试图匹配字符串的子字符串。对,现在我正在通过穷举搜索(蛮力)来做,但这需要几个小时。我希望会有一个更快更优雅的方法
namespace Sorting_Program_Ver1_1
{
class Program
{
static void Main(string[] args)
{
string[] tempStringArray; string[] dataStringArray; string[] dotdotStringArray;
List<string> myList = new List<string>();
List<string> twoDots = new List<string>();
Console.WriteLine("Starting program - initialising variables");
tempStringArray = File.ReadAllLines("C:''datadomains");
int count = 0;
for (int a = 0; a < tempStringArray.Length - 1; a++)
{
if (tempStringArray[a].Length > 0)
{
myList.Add(tempStringArray[a]);
}
}
Console.WriteLine("Adding items to string list");
for (int b = 0; b < myList.Count; b++)
{
for (int c = 0; c < myList[b].Length; c++)
{
if (myList[b][c] == '.')
{
count++;
}
}
if (count == 2)
{
twoDots.Add(myList[b]);
}
count = 0;
}
Console.WriteLine("Sorting the list into 2");
dotdotStringArray = twoDots.ToArray();
System.IO.File.WriteAllLines("C:''twoDots.txt", dotdotStringArray);
Console.WriteLine("Starting the search...");
for (int d = 0; d < twoDots.Count; d++)
{
for (int e = myList.Count - 1; e > 0; e--)
{
if (myList[e] == "")
{
Console.WriteLine("Removing empty space...");
myList.RemoveAt(e);
}
int start = myList[e].Length - twoDots[d].Length;
if (start >= 0)
{
if (twoDots[d] == myList[e].Substring(start, twoDots[d].Length))
{
if (twoDots[d] != twoDots[d])
{
Console.WriteLine("Removing...", myList[e]);
myList.RemoveAt(e);
}
}
}
}
}
Console.WriteLine("Saving to file ...");
dataStringArray = myList.ToArray();
System.IO.File.WriteAllLines("C:''myList.txt", dataStringArray);
Console.WriteLine("Saved to file");
Console.WriteLine("Exit program");
}
}
}
的例子:
mylist[0]= ".bob.com"
mylist[1]= ".steve.bob.com"
mylist[2]= ".steve.job.bob.com"
...
mylist[800000]= ".coffee.com"
substring=".bob.com"
我试图通过列表和匹配字符串与子字符串和摆脱子域。这样更清楚了吗?
在这里不能使用二分搜索,因为这意味着整个树本身处于特定的顺序(理想情况下是平衡的)。因为你想做部分比较,顺序是不重要的,因此二分查找没有帮助。
你可能想研究一下Boyer-Moore字符串搜索算法,它非常有效,特别是对于长字符串。
可以在http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f05/Artikler/09/Boyer77.pdf查看。如果你只是在谷歌上搜索"Boyer-Moore",你也应该能够找到一些有趣的链接,比如这一章来自一本关于算法的书:http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap10.htm.
还有一个最近的算法叫做Breslauer-Grossi-Mignosi(你可以在http://www.stupros.com/site/postconcept/Breslauer-Grossi-Mignosi.pdf上找到)。
如果您对字符串的完全相等感兴趣,或者如果您正在寻找从您正在搜索的字符串的开头开始的子字符串,您只能执行二进制搜索,而您不是,所以不,您不能使用二进制搜索。
如果您正在寻找字符串的任何部分作为子集,则需要构建一个Suffix Trie。实际上没有有效负载,但是您可以构建包含整个文本的所有已知后缀的Trie,这可以在文本的单个O(n)遍历中完成。这比在内存中放置一个大字符串要占用更多的内存,但是这是一种非常有效的存储与字符串相关的数据的方法。然后,搜索子字符串是对树的O(m)操作(其中m是您正在搜索的子字符串的长度),这将非常快。
如果您只想匹配整个单词,您也可以将所有单词放入HashSet<string>
,也许使用构造函数重载来忽略大小写,然后对给定单词进行O(1)检查。
后缀树(Trie变体将没有发生有效负载):http://en.wikipedia.org/wiki/Suffix_tree
在所有计算中,平衡是效率/性能和内存。您可能会为了性能而牺牲内存,或者为了内存节省而牺牲性能,但很难同时获得两者。:)