Соответствие двум большим наборам строк в C #

Question

Вот ситуация:

У меня есть веб-страница, которую я вычеркнул как строку.

У меня есть несколько полей в базе данных MSSQL.Например, модель автомобиля, у нее есть идентификатор и имя, например, Mustang или Civic.Он предварительно заполнен большинством моделей автомобилей.

Я хочу найти любое соответствие для любой строки в моей таблице моделей.Поэтому, если у меня есть Civic, Mustang и E350 в моей Таблице моделей, я хочу найти любое из трех на странице, которую я просмотрел.

Какой эффективный способ сделать это в C #.Я использую LINQ to SQL для взаимодействия с базой данных.

Имеет ли смысл создание словаря всех моделей, маркировка страницы и итерация по токенам?Или я должен просто перебрать токены и использовать предложение WHERE и спросить базу данных, есть ли совпадение?

    //Dictionary dic contains all models from the DB, with the name being the key and the id being the value...
    foreach(string pageToken in pageTokens)
    {
         if(dic.ContainsKey(pageToken)) 
         {
              //Do what I need to do
         }
    }

Оба эти метода кажутся мне ужасными.Любые предложения о том, что я должен делать?Что-то с пересечением множеств, которое я мог бы себе представить, может быть хорошим?

Ни один из этих методов не решает, что происходит, когда имя модели состоит из более чем одного слова ... как "F150 Extended Cab".Мысли об этом?

Answer 1

Поиск нескольких строк в более крупном тексте - это хорошо понятная проблема, и было проведено значительное исследование, чтобы сделать его быстрым. Два наиболее популярных и эффективных метода для этого - алгоритм Ахо-Корасика (я бы рекомендовал этот) и Алгоритм Рабина-Карпа . Они используют небольшую предварительную обработку, но являются на несколько порядков менее сложными и более быстрыми, чем метод наивных (метод наивных - наихудший O (m * n ^ 2 * p), где m - длина длинной строки [ соскоб] и n - средняя длина игл, а p - количество игл). Ахо-Корсайк линейный. Реализацию этого на C # можно найти в CodeProject бесплатно.

Редактировать: Упс, я ошибался насчет сложности Aho-Corasick - он линейный по количеству и длине входных строк + размер анализируемой строки [выделенный текст] плюс количество совпадений. Но он все равно линейный, а линейный намного лучше кубического: -).

Answer 2

Мой первый подход был бы очень простым:

foreach(string carModel in listOfCarModelsFromDatabase) {
    if(pageText.Contains(carModel) {
        // do something
    }
}

Я бы только начал беспокоиться о том, чтобы сделать это быстрее, если бы вышеприведенное не было достаточно быстрым.Список моделей автомобилей просто не может быть таким большим (<10000?), И это всего лишь одна страница текста.</p>

Answer 3

Для действительно простого решения, которое сопоставляет подстроки (которое должно работать достаточно хорошо), вы можете использовать параметризованный SQL-запрос, например:

select ModelID, ModelName
from Model
where ? like '%' + ModelName + '%'

где ? - это параметр, который заменяется всем текстом веб-страницы.

Answer 4

Вы должны использовать Regex, а не использовать токены на основе пробела.

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

Как вы строите это регулярное выражение, хотя я не уверен.

Проще говоря, вы можете просто построить Regex с каждой моделью, например

(Model 1|Model 2|Model 3) 

Но я уверен, что есть более эффективные способы сделать это в регулярном выражении.