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

Question

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

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

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

• US foo
• Американский бар (Неактивно)
• Британская летучая мышь
• Британский баз (Неактивно)
• AU womp
• AU крыса

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

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

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

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

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

Answer 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());

Answer 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);

Answer 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

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