Сравнение строк Java

Question

Я сравниваю подстроки в двух больших текстовых файлах. Очень простой, токенизация в два контейнера для токенов, по сравнению с 2 для циклов. Спектакль катастрофический! Есть ли у кого-нибудь совет или идея, как повысить производительность?

for (int s = 0; s < txtA.TokenContainer.size(); s++) { 
    String strTxtA = txtA.getSubStr(s); 
    strLengthA = txtA.getNumToken(s); 

    if (strLengthA >= dp.getMinStrLength()) { 
     int tokenFileB = 1; 

     for (int t = 0; t < txtB.TokenContainer.size(); t++) { 
      String strTxtB = txtB.getSubStr(t); 
      strLengthB = txtB.getNumToken(t); 

      if (strTxtA.equalsIgnoreCase(strTxtB)) { 
       try { 
        subStrTemp = new SubStrTemp(
         txtA.ID, txtB.ID, tokenFileA, tokenFileB, 
         (tokenFileA + strLengthA - 1), 
         (tokenFileB + strLengthB - 1)); 

        if (subStrContainer.contains(subStrTemp) == false) { 
         subStrContainer.addElement(subStrTemp); 
        } 
       } catch (Exception ex) { 
        logger.error("error"); 
       } 
      } 
      tokenFileB += strLengthB; 
     } 
     tokenFileA += strLengthA; 
    } 
} 

Вообще мой код читает два больших строк с Java Tokonizer в контейнеры A и B. А затем пытается сравнить substrings.Possision из Substrgs, которые существуют в обеих строках для хранения в векторе. Но производительность ужасна, также не знаю, как ее решить с помощью HashMap.

Answer 1

Основная проблема заключается в том, что вы просматриваете все txtB для каждого токена в txtA.

Вы должны хранить информацию о токене от txtA (например, в HashMap), а затем во втором цикле (но не вложенном) вы сравниваете строки с существующим на карте.

---

На эту же тему:

• term frequency using java program
• How to count words in java

Answer 2

Вы собираетесь присоединиться к вложенным циклам? Да, это O (n^2). А как насчет присоединения хэша? То есть, создайте карту из (нижняя) strText в t и выполняйте поиск с помощью этой карты, а не итерации по контейнеру с токеном?

Answer 3

Поместите маркеры fileA в структуру данных trie. Затем, когда tokenising fileB вы можете проверить довольно быстро, если эти токены находятся в trie. Несколько кодовых комментариев помогут.

Answer 4

сказал, что это вопрос сложности и вы алгоритм работает в O (п^2) вместо O (n) с использованием хеша.

Для улучшения второго порядка попытаться вызвать меньше функций, например, вы можете получить размер один раз

sizeB = txtB.TokenContainer.size();

Depeneds по размеру, вы можете позвонить в контейнер один раз, чтобы получить массив строк, чтобы спасти getStr ....

Рони