Как (быстро) найти самую длинную подходящую строку в C # /. Net

Question

Мне нужно выполнить некоторые операции поиска для коллекции предметов.

Сначала мне нужно проверить, есть ли прямое совпадение.Это довольно просто, так как у меня есть записи в 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

Существуют ли в структуре классы, имеющие хэшиили древовидные структуры в фоновой реализации для выполнения чего-то подобного, или мне нужно написать что-то самому?

РЕДАКТИРОВАНИЕ Пока у меня есть список, отсортированный по длине строки шаблонаи затем я просматриваю записи по очереди, чтобы увидеть, начинается ли запрос с записи.Это работает нормально для большинства ситуаций, так как у нас нет больших списков (пока), но стоит дорого для ситуаций, когда нет совпадений.

Мне не хватает словарного запаса, чтобы Google дал мнестраницы, не относящиеся к хэш-наборам, спискам и словарям.Все исследования, которые я обнаружил, указывают на древовидные структуры, но никто не указывает, есть ли уже реализация в .NET Framework или нет.

Answer 1

Леппи и Спендер верны; структура данных, которую вы хотите реализовать для эффективного решения этой проблемы, если набор данных становится большим, - это «три», или, если вы действительно любитель, DAWG - ориентированный ациклический граф слов. DAWG имеет лучшую производительность памяти, если строки имеют много общих суффиксов, но они более дороги и сложны в сборке и обновлении, поэтому начните с простого.

Ваш простой случай может создать дерево, которое выглядит так:

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

Итак, чтобы найти 023456, вы начинаете с корня, идете вниз по ветви с меткой 0, чтобы найти A, затем идете вниз по ветви 2, чтобы найти B, в этой точке нет ветви 3, так что все готово.

Между прочим, это также структура данных, которую вы использовали бы, чтобы найти самое длинное слово Эрудит из словаря и набора букв; это по сути та же проблема.

В платформе .NET нет встроенной структуры данных, но это не сложная структура данных. У меня где-то здесь лежит неизменная трия, о которой я хотел написать в блоге; если я когда-либо сделаю, я выложу ссылку здесь.

Answer 2

довольно простой способ - brute force им. я предполагаю, что у вас есть 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;
}

Answer 3

Судя по всему, вы должны использовать двоичное дерево, которое просто отсортировано по длине, а затем искать первое совпадение.Я не думаю, что что-то вроде бинарного дерева уже реализовано в C #, но быстрый поиск показывает много сайтов, где люди это сделали.

Answer 4

Вы можете просто отсканировать весь словарь на предмет наибольшего совпадения.

        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...)
            }
        }