Алгоритм поиска соответствия для заданного набора входов

Question

У меня есть набор входных множеств, каждый элемент состоит из 50 символов. Подумайте о таблице базы данных с столбцами varchar (50), каждая из которых представляет собой один набор входных данных. Количество столбцов обычно находится в пределах 5-8. Количество строк обычно составляет около 2-3 миллионов, но может составлять до 150 миллионов. Каждый столбец должен иметь ненулевое значение. Назовем эту таблицу T, и каждая ее строка RT

У меня есть второй набор входов, которые обозначают соответствующий шаблон. Точно так же, как и исходный ввод, он также может считаться таблицей базы данных с тем же фиксированным числом столбцов (плюс метаданные для сопоставления цели, но эта часть не имеет значения). Однако на этот раз только один столбец должен иметь значение, но любой из них может быть нулевым. Назовем эту таблицу M и каждый ее ряд RM. Типичный размер этой таблицы составляет 4000-5000 строк. Но может быть до 40 000.

Задача здесь для каждого RT, мы должны найти соответствующий RM. Ниже приведены правила соответствия для данного RT:

1. найдено совпадение, если все элементы RM такой же, как соответствующий элемент в РТ. (точное совпадение строк считается таким же). Если элемент имеет значение null в RM, RT не проверяется на соответствие.

2. Возможно только одно совпадение. Если идентифицировано несколько совпадений, то самый длинный RM считается правильным. Здесь можно игнорировать случай с несколькими RM с одинаковой длиной. Мы выбираем только первый из них.

Код будет работать на типичном клиенте Windows с 4 ГБ ОЗУ. Таким образом, MT может храниться в памяти, но T не может.

Я ищу технику, чтобы уменьшить количество сравнений. В частности, знаете ли вы о методе, в котором весь MT может быть проверен для данного RT. Если нет, то какой самый эффективный способ справиться с этой проблемой?

Это кодируется в .NET, и любой существующий код или библиотека для .NET очень ценится.

Спасибо,

Кемаль

ПРИМЕЧАНИЯ:

1. Это не домашнее задание. Я закончил около 20 лет назад :)

2. Существует вариант этой проблемы с регулярным выражением RM. Но для текущей версии достаточно совпадения с простой эквивалентной строкой.

3. Вот некоторые примеры:

RT = {А, В, С, D, Е}

RM1 = {А} ,,,, RM2 = {A, B ,,,} RM3 = {A ,,, D, E}

Для этого RT все это соответствует. Но из-за правила 2 мы выбираем RM3 как матч.Надеюсь, что этот пример уточняет

1. Данные Т фактически не хранятся в дБ. Это во многих форматах, включая excel, text, xml и некоторые статистические файлы SW. У нас есть структура данных, которая читает данные из их собственных форматов «на лету» и держит курсор. RT является частью этого курсора и представляет собой просто массив строк

Answer 1

Решение должно включать какое-то дерево соответствия. Цель состоит в том, чтобы пересечь дерево для каждого RT до тех пор, пока вы не достигнете листового узла, после чего у вас может быть несколько совпадений, но один из них является лучшим. Узлы в дереве - это совпадения (возможно, частичные совпадения, например {A,,,D,}), и алгоритм попадает в одну ветвь или другую, если соответствие узла выполняется или нет.

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

Предположим, что бинарное дерево достаточно хорошее. Алгоритм следует левой ветви, если соответствие выполняется, а в противном случае - в правой ветви. Так, для случая корневого узла матч {A,,,,}, и полное дерево выглядит следующим образом (каждый узел пытается сопоставить то, и имеет филиал y>, если совпадение найдено, и ветви n> если нет матча:

{A,,,,} 
y> {,B,,,} 
    y> out, matching {A,B,,,} 
    n> {,,,D,E} 
    y> out, matching {A,,,D,E} 
    n> out, matching {A,,,,} 
n> out, no match 

Компиляция этого дерева соответствия из таблицы M является проблемой сама по себе. Вы должны учитывать статистическое появление элементов в таблице T, чтобы пересечение дерева заканчивалось как можно скорее для большинства RT.