求个检索算法，按顺序最大匹配字符串，（最好是内存匹配，SQL如果有好办法也欢迎

Question

拿URL分析举例来讲HTTP://WWW.XX.COM.CN/ABC/BCD/HA/AA.HTML
分段得到 WWW.XX.COM.CN   ABC   BCD   HA  文件部分不要
数据表有 4条记录
1:WWW.XX.COM.CN
2:WWW.XX.COM.CN  ABC
3:WWW.XX.COM.CN  ABC BCD
4:WWW.XX.COM.CN  ABC BCDEF
要求检索出最大的匹配 应该得到 3HTTP://WW.COM/NEW/
分段得到 WW.COM  NEW
数据记录如下
1：WW.COM
2：WW.COM NEW
3: WW.COM NEW LINK
要返回行2.类似这种匹配查询 我想了一天 也没找到什么窍门
假定 数据表中最大段数是3 也就是说 最多匹配3级  那么恐怕也要搜索三遍才好确定。
但是数据量是很大的， 也许有几万条。请教高人给个算法或者设计 谢谢。
可以把数据放到 SQL 里 可以把多段存成多个字段 
数据表的修改很少 但是查询非常频繁
谢谢

Answer 1

几万条数据占用的内存有多大？可以考虑为第一段的域名建立一个Hash类型的数据结构，如Dictionary之类，这样可以加速第一段的查找，而且是内存中查找。
根据第一段的键值，找到以第一段开头的所有数据，再进行后续的查找。

Answer 2

写一个方法返回匹配的个数private int GetCount(string str,string pattern)//str参数是数据库中的某条记录，pattern是例如你上面写的HTTP://WWW.XX.COM.CN/ABC/BCD/HA/AA.HTML之类的东东
{
int count=0;
string[] ss=pattern.Split("/");//用正则也可以
ArrayList al=new ArrayList(ss);
把str也Split一下，然后循环看这些字符串是否在al中，如果是,count就加1
return count;
}取最后返回值最大的str就是了。

Answer 3

数据库结构是怎么样的?
--引用开始---
数据表有 4条记录 
HTTP://WWW.XX.COM.CN/ABC/BCD/HA/AA.HTML 
分段得到 WWW.XX.COM.CN  ABC  BCD  HA  文件部分不要 
数据表有 4条记录 
1:WWW.XX.COM.CN 
2:WWW.XX.COM.CN  ABC 
3:WWW.XX.COM.CN  ABC BCD 
4:WWW.XX.COM.CN  ABC BCDEF 
要求检索出最大的匹配 应该得到 3 HTTP://WW.COM/NEW/ 
分段得到 WW.COM  NEW 
数据记录如下 
1：WW.COM 
2：WW.COM NEW 
3: WW.COM NEW LINK 
要返回行2. 
--引用结束---如果在一个字段里, 试试 like 查找, 然后以长度差的绝对值 排序无测试环境,未作测试 ...

Answer 4

using System.Text.RegularExpressions;static void Main(string[] args)
{
    //你的URL
    string site = "HTTP://WWW.XX.COM.CN/ABC/BCD/HA/AA.HTML";
    Regex r1 = new Regex(@"(?<=/)[^/].+?(?=/)");
    MatchCollection mc1 = r1.Matches(site);    string[] sc = new string[mc1.Count];
    for (int i = 0; i < mc1.Count; i++)
    {
        sc[i] = mc1[i].Value;
    }
    string pattern = string.Join("|", sc);    Regex r2 = new Regex(pattern);
    //你的记录
    string[] recoders = { "WWW.XX.COM.CN", "WWW.XX.COM.CN  ABC", "WWW.XX.COM.CN  ABC BCD", "WWW.XX.COM.CN  ABC BCDEF" };    int[] maxMatch = new int[recoders.Length];    for (int i = 0; i < recoders.Length; i++)
    {
        MatchCollection mc2 = r2.Matches(recoders[i]);
        maxMatch[i] = mc2.Count;
    }    int maxIndex = 0;
    for (int i = 1; i < maxMatch.Length-1; i++)
    {
        if (maxMatch[i] > maxMatch[i - 1])
            maxIndex = i;
    }
    Console.WriteLine(recoders[maxIndex]);
}看看我能得几分，1oo? n_n

Answer 5

建立一个缓存，缓存RecordIndex
在初始化RecordIndex没有考虑时间复杂度，如果需要可以写一部分代码来实现
这里没有实现缓存，缓存要依赖于数据库，也可以在更新数据库的时候更新下RecordIndex ，例如增加一条数据库记录的同时调用下AddRecord /// <summary>
/// Class1 的摘要说明。
/// </summary>
class Class1
{
/// <summary>
/// 应用程序的主入口点。
/// </summary>
[STAThread]
static void Main(string[] args)
{
// //Console.WriteLine( Marshal.SizeOf( typeof(AsMonitorNumAtActivity )));
//
// XmlDocument  doc = new XmlDocument();
// doc.Load(@"C:\111.xml");
// XmlNodeList list = doc.SelectNodes(@"NewDataSet/CalendarNumStat");
// Console.WriteLine( list.Count ); string[] recoders = { "WWW.XX.COM.CN", "WWW.XX.COM.CN ABC", 
"WWW.XX.COM.CN ABC BCD", "WWW.XX.COM.CN ABC BCDEF" }; RecordIndex  Index = new RecordIndex(recoders); Console.WriteLine(Index.Match("WWW.XX.COM.CN ABC"));

Console.ReadLine();
//
// TODO: 在此处添加代码以启动应用程序
//
} }
public class RecordIndex
{
//有幻型的话可以使用List<RecordIndex>
private class _RecordIndexs:ArrayList
{
public override int IndexOf(object value)
{
if( value is RecordIndex )
return base.IndexOf (value);
else if( value is string )
{
for( int i =0 ;i< Count ;i++)
{
if( (this[i] as RecordIndex).Subsection.Equals( value))
return i;
}
return -1;
}
return -1;
} }
/// <summary>
/// 本级索引位置的关键字 例如 WWW.XX.COM.CN 
/// </summary>
private string Subsection;
private _RecordIndexs RecordIndexs = new _RecordIndexs();
/// <summary>
/// 索引本身是否也是一个值
/// </summary>
private bool IndexIsValue=false; private RecordIndex ( string Subsection )
{
this.Subsection = Subsection;
} /// <summary>
/// 根据数据库中的数据记录构建索引记录 假设Records已经有序
/// </summary>
public RecordIndex(string[] Records)
{
foreach( string s in Records )
{
this.AddRecord(s);
}
}
/// <summary>
/// 向索引结构添加一条记录 用空格分割
/// </summary>
public void AddRecord(string Record)
{
string[] subRecords = Record.Split(' ');//用空格分割
AddRecord( subRecords , 0);
}
private void AddRecord( string[] subRecords , int Index)
{
if( Index >= subRecords.Length ) return;
string section = subRecords[Index];
if(section.Trim().Length == 0)
{
this.AddRecord(subRecords ,Index + section.Length );
}
int I = RecordIndexs.IndexOf(section);
RecordIndex subIndex;
if( I>=0 )
{
subIndex = RecordIndexs[I] as RecordIndex;
}
else
{
subIndex = new RecordIndex(section);
this.RecordIndexs.Add(subIndex);
}
if( subRecords.Length == Index + 1)
subIndex.IndexIsValue = true;
else
subIndex.AddRecord( subRecords , Index + 1); }
public string Match( string Record)
{
return Match (Record.Trim().Split(' '));
}
public string Match( string[] Records)
{
ArrayList PathStrings = new ArrayList();

foreach( RecordIndex X in this.RecordIndexs)
{
if( X.Match(Records,0 , PathStrings))
break;
}
string ret = string.Empty;
foreach( string s in PathStrings)
{
ret += s+" ";
}
return ret;
}
private bool Match( string[] Records ,int Index , ArrayList PathStrings)
{
if( Records.Length <= Index) return false;
string Section = Records[Index];
if( this.Subsection.Equals( Section ))
{
if( Records.Length == Index + 1)
{
if( IndexIsValue )
{
PathStrings.Add( this.Subsection );
return true;
}
                    return false; //这里意思是数据库中没有完全是查找串的子串的记录 如果这种情况也可以匹配 返回True即可
}
else
{
PathStrings.Add( this.Subsection );
foreach( RecordIndex X in this.RecordIndexs)
{
if( X.Match(Records,Index + 1 , PathStrings))
return true;
}
}
}
return false;
}
}

Answer 6

这里写的比较毛躁，如果再细化的话可以采用二分查找，不过需要索引也有序
类似下面的代码 ，可以再提升一下性能                    foreach( RecordIndex X in this.RecordIndexs)
                    {
                        if( X.Match(Records,Index + 1 , PathStrings))
                            return true;
                    }

Answer 7

NATTY的得分再另外的帖子，不会亏了你的哦