LINQ Чтобы найти частичные совпадения

Question

Имейте слова из OCR и вам нужен список близких совпадений. Может жить без maxFrom. Пример кода - грубая сила, но, надеюсь, он определяет это требование. Против списка 600 000 это занимает 2 секунды. FTSword.Word - это строка.

В идеале «findd» предоставит дополнительный кредит на второй d. И как только он находит i, тогда f не получает никакого кредита. Грубая сила, я могу это сделать. Я ищу, чтобы сделать это 2 секунды вниз. Будет проверять и сообщать о любом предлагаемом решении.

Вопрос ?? является. Как сделать это быстрее? (И умнее)

Благодаря

  char[] find = new char[] { 'f', 'i', 'n', 'd' }; 
      char[] word; 
      int maxFrom = 10; 
      int minMatch = 3; 
      int count; 
      List<FTSword> matchWords = new List<FTSword>(); 
      foreach (FTSword ftsw in fTSwords) 
      { 
       if (ftsw.Word.Length < maxFrom) 
       { 
        word = ftsw.Word.ToCharArray(); 
        count = 0; 
        foreach (char fc in find) 
        { 
         foreach (char wc in word) 
         { 
          if (char.ToLower(wc) == char.ToLower(fc)) 
          { 
           count++; 
           break; 
          } 
         } 
        } 
        if (count >= minMatch) 
        { 
         // Debug.WriteLine(count.ToString() + ftsw.Word); 
         matchWords.Add(ftsw); 
        } 
       } 
      } 
      Debug.WriteLine(matchWords.Count.ToString()); 

Answer 1

Ваш основной алгоритм в настоящее время O (N^2), так как у вас есть два вложенных цикл подберут символы. Вы можете легко сделать эту часть O (п) с помощью словаря, который содержит счетчики символов для каждого символа в find строки:

string find = "find"; 
var findMap = new Dictionary<char, int>(); 
foreach (char c in find) 
{ 
    if (findMap.ContainsKey(c)) 
    { 
     findMap[c] = findMap[c] + 1; 
    } 
    else 
     findMap.Add(c, 1); 
} 
//findMap is pre-generated once 

string word = "pint"; 
int count = 0; 

//runs for each word in list, now in O(n) 
foreach(char c in word) 
{ 
    int charCount; 
    if(findMap.TryGetValue(c, out charCount)) 
    { 
     if(charCount > 0) 
     { 
      charCount--; 
      findMap[c] = charCount; 
      count++; 
     } 
    } 
} 

Answer 2

Вы можете удалить char.ToLower() на ФХ, если вы убедитесь, что это в нижнем регистре перед вами Начало.

Вы также можете попробовать использовать IndexOf(), чтобы найти первое (а затем последующее вхождение символа), поскольку реализация BCL может быть внутренне быстрее, чем вы можете управлять с помощью своего собственного цикла.

Вы также можете попробовать запустить свою петлю в обратном направлении, которое может обеспечить ускорение:

for (int i = arr.Length - 1; i >= 0; i--) 

Но на самом деле, для распознавания текста, почему бы вы подытожить соответствие символов из произвольных позиций в строке вместо того, чтобы делать истинное редактирование расстояние, например Damerau-Levenshtein?