Java - список ключевых слов в другом списке строк

Question

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

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

E.g.

список

Ключевые слова = FIRSTNAME, LASTNAME, CURRENCY & FUND

список данных = HUSBANDFIRSTNAME, HUSBANDLASTNAME, WIFEFIRSTNAME, SOURCECURRENCY & CURRENCYRATE.

Из выше примера, я хотел бы сделать целевой список ключевых слов с FIRSTNAME, LASTNAME & CURRENCY, однако FUND не должен прийти, как не существует в данных список.

У меня есть решение ниже, которое работает с использованием двух циклов (один внутри другого) и проверки с помощью метода String содержит, но я бы хотел избежать двух циклов, особенно внутри внутри.

for (int i=0; i<dataList.size();i++) { 
     for (int j=0; j<keywordsList.size();j++) { 
      if (dataList.get(i).contains(keywordsList.get(j))) { 
        targetSet.add(keywordsList.get(j)); 
        break; 
      } 
     } 
    } 

Есть ли другое альтернативное решение для моей проблемы?

Answer 1

Ниже приведено одноцелевое приближение с использованием regex. Вы строите шаблон, используя свои ключевые слова, а затем итерируете через свой dataList и видите, можете ли вы найти совпадение.

public static void main(String[] args) throws Exception { 
    List<String> keywords = new ArrayList(Arrays.asList("FIRSTNAME", "LASTNAME", "CURRENCY", "FUND")); 
    List<String> dataList = new ArrayList(Arrays.asList("HUSBANDFIRSTNAME", "HUSBANDLASTNAME", "WIFEFIRSTNAME", "SOURCECURRENCY", "CURRENCYRATE")); 
    Set<String> targetSet = new HashSet(); 

    String pattern = String.join("|", keywords); 
    for (String data : dataList) { 
     Matcher matcher = Pattern.compile(pattern).matcher(data); 
     if (matcher.find()) { 
      targetSet.add(matcher.group()); 
     } 
    } 

    System.out.println(targetSet); 
} 

Результаты:

[CURRENCY, LASTNAME, FIRSTNAME] 

Answer 2

Попробуйте алгоритм Aho-Corasick. Этот алгоритм может получить счет появления каждого ключевого слова в данных (вам просто нужно, появилось оно или нет).

Сложность - O(Sum(Length(Keyword)) + Length(Data) + Count(number of match)).

Вот wiki-page:

В информатике, алгоритм Ахо-Corasick является строкой поиска алгоритм, изобретенный Альфред В. Ахо и Маргарет Дж Corasick. Это своего рода алгоритм сопоставления словаря, который определяет элементы конечного набора строк («словарь») во входном тексте. Он соответствует всем шаблонам одновременно. Сложность алгоритма является линейной по длине шаблонов плюс длина искомого текста плюс количество выходных совпадений.

Я реализовал его (около 200 строк) лет назад для аналогичного случая, и он хорошо работает.

Если вы просто заботитесь ключевым словом появился или нет, вы можете изменить этот алгоритм для случая с лучшей сложностью:

O(Sum(Length(Keyword)) + Length(Data)).

Вы можете найти реализацию этого алгоритма из Интернета повсюду, но я думаю, вам хорошо понять этот алгоритм и реализовать его самостоятельно.

---

EDIT:

Я думаю, что вы хотите устранить две петли, так что нам нужно найти все ключевые слова в одной петле. Мы называем это Set Match Problem тем, что набор шаблонов (ключевых слов) соответствует тексту (данным). Вы хотите решить Set Match Problem, тогда вы должны выбрать Aho–Corasick algorithm, который специально разработан для этого случая.Таким образом, мы получим одно решение цикла:

for (int i=0; i < dataList.size(); i++) {  
    targetSet.addAll(Ac.run(keywordsList)); 
} 

Вы можете найти реализацию из here.