如何(快速)在C#/ .Net中找到最长的匹配字符串

Question

我需要对一组项目进行一些查找操作.

首先,我需要看看是否有直接匹配.这很简单,因为我有一个条目Dictionary<String,MyObjectType>,所以我可以去dictionary["valuetofind"].

但是如果没有直接匹配,那么我需要进行一个start-with匹配,但它必须是返回的最长匹配:

记录示例:

String   Record
0        A
01       B
012      D
02       B
03       C

查询示例:

Query         Result 
0             A    - Because 0   is the longest match
01            B    - Because 01  is the longest match
023456        B    - Because 02  is the longest match
012           D    - Because 012 is the longest match
0123456       D    - Because 012 is the longest match
03456         C    - Because 03  is the longest match
04            A    - Because 0   is the longest match
0456          A    - Because 0   is the longest match
1             Null - No Match

框架中是否有类在后台实现中具有哈希或树结构来执行此类操作,或者我是否需要自己编写某些内容？

编辑 到目前为止我所拥有的是按照模式字符串的长度排序的列表,然后我逐个查看条目以查看查询是否以记录开头.这适用于大多数情况,因为我们没有大型列表(但是),但在没有匹配的情况下确实有昂贵的成本.

我缺乏词汇来让google给我一些与哈希集,列表和词典无关的页面.我发现的所有研究都指向基于树的结构,但没有人指出.NET Framework中是否已有实现.

Answer 1

Leppie和Spender是正确的; 如果数据集变大,你想要有效地解决这个问题的数据结构是一个"trie",或者,如果你真的是buff,那就是一个DAWG - 一个有向的非循环字图.如果字符串有许多常见的后缀但是它们更昂贵且难以构建和更新,那么DAWG具有更好的内存性能,所以从trie开始.

你的简单案例会产生一个看起来像这样的特里:

           ROOT
            |
           0|
            |
            A
          / | \
         /  |  \
       1/  2|  3\
       /    |    \
      /     |     \
     B      B      C
     |
    2|
     |
     D

所以要查找023456,你从根开始,按下标记为0的分支找到A,然后沿着分支2找到B,那时没有分支3,所以你已经完成了.

顺便说一句,这也是你用来找到字典和一组字母的最长Scrabble字的数据结构; 这基本上是同样的问题.

.NET框架中没有内置的trie数据结构,但构建起来并不困难.我有一个不可改变的特里在我身边的某个地方,我一直想写博客; 如果我这样做,我会在这里发布一个链接.