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

Question

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

c#collections

3

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

首先，我需要查看是否存在直接匹配项。这很简单，因为我有一个条目在 Dictionary<String,MyObjectType> 中，所以我只需要执行 dictionary["valuetofind"]。

但是，如果没有直接匹配项，则需要执行以某个值开头的匹配，但必须返回最长的匹配项：

记录示例：

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

有没有在框架中有哈希或树结构的类来实现这样的功能，还是我需要自己编写？目前我所做的是按模式字符串长度排序列表，然后逐个检查条目以查看查询是否以记录开头。对于大多数情况，这种方法效果不错，因为我们没有很长的列表（但），但在没有匹配项的情况下会产生昂贵的成本。我缺乏词汇来让谷歌给我与哈希集、列表和字典无关的页面。我找到的所有研究都指向基于树的结构，但没有指出.NET Framework中是否已经有了实现。

- My Other Me

1

请查看以下两个网址：http://stackoverflow.com/questions/2765786/quickly-or-concisely-determine-the-longest-string-per-column-in-a-row-based-data 和 https://dev59.com/R1DTa4cB1Zd3GeqPKp5i。 - Glory Raj

1

下面的字典方法可能是O(n^2 logn)。使用Trie树可能会更好，只需要O(n logn)的时间复杂度。 - leppie

如果你需要搜索一个非常大的集合，那么类似Trie的数据结构是解决这个问题最快的方法。http://en.wikipedia.org/wiki/Trie - spender

1

@leppie：你的顺序近似中的对数项是从哪里来的？一个良好构建的trie可以在O(m)时间内搜索长度为m的字符串；trie中的节点数量不是一个因素。 - Eric Lippert

@EricLippert：你说得对。不确定我当时在想什么；p 我知道第一个只是根据“包含”而不是“以...开始”错误地估算的。 - leppie

4个回答

1

一个相对简单的方法是通过“暴力破解”它们。我假设你有一个名为Dictionary<string, string> _lookupTable的字典，用于保存你的查找表。

string Find(string query)
{
    var retval = null;
    while(!string.IsNullOrEmpty(query) && retval == null)
    {
        if(!_lookupTable.TryGetValue(query, out retval))
            query = query.Substring(0, query.Length-1);
    }
    return retval;
}

- esskar

1

对我而言是可行的。我用这个实现进行了一些测试，它对我们的需求来说足够快速了。 - My Other Me

0

看起来，你应该使用一个二叉树，它只是按长度排序，然后查找第一个匹配项。我不认为像二叉树这样的东西已经在C#中实现了，但是快速搜索会发现许多人已经这样做了。

- hcb

0

你可以扫描整个字典以获取最长匹配。

        string sQuery = "01234";

        int iMaxLength = 0;
        foreach (KeyValuePair<String, String> kVP in mD)
        {
            if (sQuery.Contains(kVP.Value) && (kVP.Value.Length > iMaxLength))
            {
                iMaxLength = kVP.Value.Length
                result = (whatever...)
            }
        }

- Shai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Lippert · Accepted Answer

Leppie和Spender是正确的；如果数据集变得很大，你想要实现的数据结构以有效地解决这个问题是“trie”，或者，如果你真的很厉害，是一个DAWG——一个有向无环词图。如果字符串有许多共同的后缀，DAWG具有更好的内存性能，但它们更昂贵和难以构建和更新，所以从trie开始。

你简单的情况将创建一个trie，看起来像这样：

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

要查找023456，您需要从根开始，沿着标记为0的分支向下找到A，然后沿着2的分支找到B，此时没有分支3，所以您完成了查找。

顺便说一句，这也是您在给定字典和一组字母的情况下查找最长Scrabble单词所使用的数据结构；本质上是相同的问题。

.NET框架中没有内置Trie数据结构，但是构建Trie不是一个困难的数据结构。我这里有一个不可变的Trie，我一直在想写一篇博客介绍它；如果我写了，我会在这里发布链接。