Вопрос по pattern-matching, string, regex, java, duplicates – Как обнаружить повторяющиеся слова из строки в Java?

0

Как можно обнаружить повторяющееся слово в строке?

например & quot; это тестовое сообщение для дубликата теста & quot; содержит один тест слова дубликата.

Здесь цель состоит в том, чтобы обнаружить все повторяющиеся слова, которые встречаются в строке.

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

Ваш Ответ

2   ответа
3

Следующий код Java решает проблему обнаружения дубликатов из строки. Не должно быть никаких проблем, если повторяющееся слово разделено символами новой строки или пунктуации.

    String duplicatePattern = "(?i)\\b(\\w+)\\b[\\w\\W]*\\b\\1\\b";
    Pattern p = Pattern.compile(duplicatePattern);
    String phrase = "this is#$;%@;<>?|\\` p is a is Test\n of duplicate test";
    Matcher m = p.matcher(phrase);
    String val = null;
    while (m.find()) {
        val = m.group();
        System.out.println("Matching segment is \"" + val + "\"");
        System.out.println("Duplicate word: " + m.group(1)+ "\n");
    }

Вывод кода будет:

Matching segment is "is#$;%@;<>?|\` p is a is"
Duplicate word: is

Matching segment is "Test
 of duplicate test"
Duplicate word: Test

Здесь оператор m.group (1) представляет строку, сопоставленную с 1-й группой шаблона [здесь, это '(\\ w +)].

Вы имеете в виду, что он ответил на свой вопрос ...
Насколько хорошо это масштабируется?
@DebadyutiMaiti - меня больше не волнуют крайние случаи, а то, как это происходит при увеличении объема текста (см. Ответ Стивена С. выше)
@BrianAgnew Если у вас возникли проблемы с кодом для некоторых крайних тестовых случаев, пожалуйста, сообщите мне. Debadyuti Maiti
8

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

Да, но, как я уже сказал, пространство над головойO(N); т.е. пропорционально размеру ввода.
@StephenC Но можете ли вы предоставить любую ссылку, которая показывает O (N ^ 2) сложность времени? Потому что эта ссылка утверждает, что это O (N).stackoverflow.com/questions/5892115/… Debadyuti Maiti
Тогда компромисс снова - время против пространства, так как вам нужна вспомогательная структура данных для обнаружения
@StephenC Можете ли вы привести пример кода [т.е. имеем дело с HashSet]? Поскольку я думаю, что для «разделения ввода на слова» я должен использовать регулярное выражение. Опять же, каждое слово должно быть изменено на lowerCase или upperCase, в противном случае я не думаю, что HashSet сможет различать дублирующиеся строки со смешанными падежами. Таким образом, для большого ввода созданные объекты String [только для сравнения] будут очень высокими, & amp; для изменения нижнего регистра разделение ввода на слова в целом должно привести к некоторому снижению производительности. Debadyuti Maiti
Этот ответ имеет в видуreal регулярные выражения (в теоретическом смысле). Настоящее регулярное выражение не допускает обратных ссылок. И если вы мне не верите, я предлагаю вам провести несколько экспериментов, чтобы увидеть, как производительность вашего регулярного выражения масштабируется для больших и больших входных строк.

Похожие вопросы