Алгоритм поиска очень распространенных вхождений подстрок в наборе коротких строк

#c# #string #algorithm

#c# #строка #алгоритм

Вопрос:

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

Я создаю интерфейс и хотел бы представить пользователю раскрывающийся список фильтрации этих подстрок.

Например, если у меня есть входные строки:

US foo
US bar (неактивный)
UK bat
UK baz (неактивный)
AU womp
AU rat

Я хочу вернуться:

США
Великобритания
AU
Неактивный

Мои первые мысли — иметь пороговый параметр и список разделителей. Для приведенного выше я мог бы сказать, что порог = .3, а разделителями являются пробелы, (, и ) .

Затем выполните string.split с использованием разделителей и используйте структуру данных, подобную set, которая подсчитывает повторяющиеся элементы (?)…

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

Ответ №1:

Эта проблема является хорошим кандидатом для подхода Linq:

 var words = from s in listOfStrings
            from word in s.Split(new[] { ' ', '(', ')' }, StringSplitOptions.RemoveEmptyEntries)
            group word by word;
var dic = words.ToDictionary(g => g.Key, g => g.Count());

1. Еще лучше, когда у вас есть группы, выполните «где count> пороговое значение» и «порядок по количеству», и тогда вы получите запрос, который приведет именно к тому, что хочет пользователь.

2. я просто хочу еще раз поблагодарить — это прекрасно сработало и помогло мне «думать о linq»

Ответ №2:

Простым способом было бы что-то вроде того, что вы указали. Dictionary<String, int> Настройте для хранения ваших данных. Тогда это просто:

 for each word in string
   if word is in dictionary
      increment dictionary value
   else
      add to dictionary with value of 1

Затем просто отфильтруйте этот словарь на основе порогового значения или верните записи, отсортированные по количеству. Вы также можете создать «список игнорирования» с общими словами, которые вы не хотите отслеживать.

Кроме того, если вы хотите нечувствительность к регистру, создайте словарь следующим образом: new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

1. хорошо — или я мог бы спроецировать отношение itme к его количеству, а затем отсортировать по нему, предоставив мне элементы и их процентное соотношение по убыванию… вероятно, это стандартная статистическая функция.. может быть, кто-нибудь укажет на это (это напоминает мне кое-что, что я читал, когда однажды просматривал функции Excel «для развлечения»)

2. Вы можете представить его несколькими способами. Если вам просто нужен процент от строки в терминах общего количества токенов, просто разделите количество на общее число. Некоторым людям нравится выражать это в процентах, где 100% = наиболее частое слово, и в этом случае вы делите каждое количество на количество раз, когда было найдено наиболее частое слово. Это сильно зависит от вашего варианта использования.

Ответ №3:

 var input = new List<string>();
input.Add("Foo"); // I'd go for splitting by delimiters as well
input.Add("Bar");
input.Add("Foo");
var results = input.Distinct(); // -> Foo, Bar

Я не совсем уверен, каков ваш порог.