是否可以对字典字符串键进行部分字符串匹配？

Question

我的代码中有一个 Dictionary> ，我按以下方式使用它：

Key           Values  
2011-07-15    1, 2, 3
2011-07-20    4, 5, 6
2010-02-11    7, 8, 9

我的代码需要能够查询与键中特定子字符串匹配的所有值。例如，如果我有子字符串 2011-07 它应该返回值 {1, 2, 3, 4, 5, 6}。 11 的子字符串应返回 1-9 中的所有 ID。

谁能推荐一种简洁的方法来实现这一目标？或者提供更好的数据结构来检索这些信息？

Answer 1

我会做一个扩展方法：

public static class DictionaryExt
{
    public static IEnumerable<T> PartialMatch<T>(this Dictionary<string, T> dictionary, string partialKey)
    {
        // This, or use a RegEx or whatever.
        IEnumerable<string> fullMatchingKeys = 
            dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey));

        List<T> returnedValues = new List<T>();

        foreach (string currentKey in fullMatchingKeys)
        {
            returnedValues.Add(dictionary[currentKey]);
        }

        return returnedValues;
    }
}

向字典添加值的“成本”不会改变，但检索的成本会更高，但前提是您知道要进行部分匹配。

顺便说一句，我确信您可以将其转换为单个 Lambda 表达式，但概念保持不变。

编辑：在您的示例中，此方法将返回 2 个值列表，但您可以更改它以合并列表。这是您可以执行的扩展方法：

public static IEnumerable<T> PartialMatch<T>(
    this Dictionary<string, IEnumerable<T>> dictionary,
    string partialKey)
{
    // This, or use a RegEx or whatever.
    IEnumerable<string> fullMatchingKeys = 
        dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey));

    List<T> returnedValues = new List<T>();

    foreach (string currentKey in fullMatchingKeys)
    {
        returnedValues.AddRange(dictionary[currentKey]);
    }

    return returnedValues;
}

编辑 2：想想看，您还可以使其更通用。使用下一个扩展方法，它可以在任何字典上工作，只要您提供一个比较器来检查“部分匹配”的含义：

public static IEnumerable<TValue> PartialMatch<TKey, TValue>(
    this Dictionary<TKey, IEnumerable<TValue>> dictionary,
    TKey partialKey,
    Func<TKey, TKey, bool> comparer)
{
    // This, or use a RegEx or whatever.
    IEnumerable<TKey> fullMatchingKeys = 
        dictionary.Keys.Where(currentKey => comparer(partialKey, currentKey));

    List<TValue> returnedValues = new List<TValue>();

    foreach (TKey currentKey in fullMatchingKeys)
    {
        returnedValues.AddRange(dictionary[currentKey]);
    }

    return returnedValues;
}

Answer 2

您正在寻找简洁的答案。如果没有低级别的文本索引（我不知道任何专门的 .Net 类），我认为字典仍然是您最好的选择。使用如下内容进行查询：

myDictionary.Where(kvp => kvp.Key.Contains("11")).SelectMany(kvp => kvp.Value);

您必须搜索所有键无论如何，对于通用子字符串，没有一些非常酷的魔法（.Net 未提供），因此 LINQ 在这里不会对您造成太大伤害。

Answer 3

如果 Dictionary 使用内部哈希值，那么你就不走运了，因为相似的字符串会产生不同的哈希值。我刚刚在周末用 C 语言实现了这个要求的解决方案，面试测试/作业。我使用排序数组作为底层结构 - 昂贵的插入，但快速查找（使用二分搜索）。要查找键以前缀开头的所有条目，我会找到第一个，然后继续下一个，下一个...对于一般子字符串，即不仅仅是前缀，我的解决方案将不起作用。目前我不知道对“常规子字符串”搜索有何建议。

Answer 4

你可以拥有三本字典。年、月、日。

请注意，当您将项目添加到三个词典时，您并不是在复制这些项目。

当您使用两个键拉出项目时，可以使用 LINQ 扩展方法 Intersect() 来获取与两个键匹配的项目（在两个结果集上使用 Intersect）。

警告，这样做不会导致执行速度最快的代码。

Answer 5

一种简洁的方法是使用多值映射。

例如：

Dictionary<string, Dictionary<string, List<int>>

为什么不将 2011-07 存储为键，将 15 存储为内部字典键，将 1,2,3 存储为值。

地图["2011-07"]["15"]= {1,2,3};

如果您只想要 2011-07 您可以通过遍历获取其他字典中的所有内容。

map["2011-07"] // 将返回 u 1,2,3,4,5,6

，如果您想要前往特定日期，2011-07-15 这将仅返回 1,2,3

foreach(var element in map["2011-07"]){

     var values = element.values; // and you can append them to a list.

}

，如果您需要年/月/日， ，您将需要多级字典。或者您也可以使用树。