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

拿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
要求检索出最大的匹配 应该得到 3

HTTP://WW.COM/NEW/
分段得到 WW.COM  NEW
数据记录如下
1：WW.COM
2：WW.COM NEW
3: WW.COM NEW LINK
要返回行2.

类似这种匹配查询 我想了一天 也没找到什么窍门
假定 数据表中最大段数是3 也就是说 最多匹配3级  那么恐怕也要搜索三遍才好确定。
但是数据量是很大的， 也许有几万条。

请教高人给个算法或者设计 谢谢。
可以把数据放到 SQL 里 可以把多段存成多个字段 
数据表的修改很少 但是查询非常频繁
谢谢

24 个解决方案

#1

如果要考虑性能的话  找人写正则吧

#2

第一次按第一段进行搜索，后面的搜索在第一次的匹配结果上进行，依次类推。
如果按第一段搜索后的结果平均数量不多的话，可以将第一段搜索的结果全部读入内存，后面的搜索可以在内存中进行。

#3

楼上 我基本就是这么想的 但是感觉在数万记录中这么一遍一遍的找 太慢了  我这里需要及时处理转向，所以不能太慢，一般都是几十个请求一下发过来，要赶快处理好发回去。

#4

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

#5

写一个方法返回匹配的个数

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就是了。

#6

mark

#7

同意一楼，写正则效率是最高的

#8

up

#9

如果机子好，每读一行数据就开个线程去计算算了

#10

学习了。帮顶一下！

#11

数据库结构是怎么样的?
--引用开始---
数据表有 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 查找, 然后以 长度差的绝对值 排序

无测试环境,未作测试 ...

#12

顶一下。

#13

关注

#14

顶！

#15

欢迎加入QQ交流群71945118

#16

嗯,看完之后基本上同意一楼,正则应该比较快,二楼的方法也很好,可以结合一下嘛

#17

这个问题实在是太简单了！

标记一下先，等下搞定

#18

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

#19

18楼的代码好像是对的，但对于性能要求比较高的时候并不合适。

比较快速的方法是建立多级索引 然后根据索引查找匹配

#20

引用 19 楼 crossrowman 的回复:

18楼的代码好像是对的，但对于性能要求比较高的时候并不合适。 

比较快速的方法是建立多级索引 然后根据索引查找匹配 

你写一个我瞧瞧

#21

建立一个缓存，缓存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;
		}
	}

#22

这里写的比较毛躁，如果再细化的话可以采用二分查找，不过需要索引也有序
类似下面的代码 ，可以再提升一下性能

                    foreach( RecordIndex X in this.RecordIndexs)
                    {
                        if( X.Match(Records,Index + 1 , PathStrings))
                            return true;
                    }

#23

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

#24

LOOK