Java: Policz liczbę wystąpień słowa w ciągu znaków

Wprowadzenie

Zliczanie liczby wystąpień słów w ciągu jest dość łatwym zadaniem, ale można to zrobić na kilka sposobów. Musisz również wziąć pod uwagę wydajność metody, ponieważ zazwyczaj będziesz chciał użyć zautomatyzowanych narzędzi, gdy nie chcesz wykonywać pracy ręcznej – tj. gdy przestrzeń wyszukiwania jest duża.

W tym przewodniku dowiesz się, jak zliczyć liczbę wystąpień słów w ciągu znaków w Javie:

String searchText = "Your body may be chrome, but the heart never changes. It wants what it wants.";
String targetWord = "wants";

Poszukamy liczby wystąpień znaku targetWordZa pomocą String.split(), Collections.frequency() i wyrażenia regularne.

Policz wystąpienia słów w ciągu za pomocą String.split()

Najprostszym sposobem na zliczenie występowania słowa docelowego w ciągu jest podzielenie ciągu na każde słowo i iteracja przez tablicę, zwiększając liczbę wordCount na każdym meczu. Zwróć uwagę, że gdy słowo ma wokół siebie jakiś rodzaj znaków interpunkcyjnych, na przykład wants. na końcu zdania – prosty podział na poziomie słów właściwie potraktuje wants i wants. jako osobne słowa!

Aby obejść ten problem, możesz łatwo usunąć wszystkie znaki interpunkcyjne ze zdania zanim dzielenie go:

String[] words = searchText.replaceAll("p{Punct}", "").split(" ");

int wordCount = 0;
for (int i=0; i < words.length; i++)
    if (words[i].equals(targetWord))
        wordCount++;
System.out.println(wordCount);

W for pętli, po prostu iterujemy po tablicy, sprawdzając, czy element pod każdym indeksem jest równy targetWord. Jeśli tak, zwiększamy wordCount, który pod koniec egzekucji drukuje:

2

Policz wystąpienia słów w ciągu za pomocą Kolekcje.częstotliwość()

Połączenia Collections.frequency() metoda zapewnia znacznie czystszą implementację wyższego poziomu, która oddziela proste for pętla i sprawdza zarówno tożsamość (czy obiekt is inny przedmiot) i równość (czy przedmiot jest równy innemu przedmiotowi, w zależności od cech jakościowych tego przedmiotu).

Połączenia frequency() metoda przyjmuje listę do przeszukania oraz obiekt docelowy i działa również dla wszystkich innych obiektów, gdzie zachowanie zależy od tego, jak sam obiekt implementuje equals(). W przypadku strun, equals() czeki na zawartość ciągu:

searchText = searchText.replaceAll("p{Punct}", "");

int wordCount = Collections.frequency(Arrays.asList(searchText.split(" ")), targetWord);
System.out.println(wordCount);

Tutaj przekonwertowaliśmy tablicę uzyskaną z split() w Javie ArrayList, używając pomocnika asList() metoda Arrays klasa. Operacja redukcji frequency() zwraca liczbę całkowitą oznaczającą częstość targetWord na liście i skutkuje:

2

Wystąpienia słów w ciągu z Dopasowywanie (wyrażenia regularne – RegEx)

Na koniec możesz użyć wyrażeń regularnych, aby wyszukać wzorce i policzyć liczbę dopasowanych wzorców. Wyrażenia regularne są do tego stworzone, więc jest to bardzo naturalne dopasowanie do tego zadania. W Javie Pattern klasa służy do reprezentowania i kompilowania wyrażeń regularnych, a Matcher klasa służy do wyszukiwania i dopasowywania wzorców.

Używając RegEx, możemy zakodować niezmienność interpunkcji w samym wyrażeniu, więc nie ma potrzeby zewnętrznego formatowania ciągu lub usuwania interpunkcji, co jest preferowane w przypadku dużych tekstów, gdzie przechowywanie innej zmienionej wersji w pamięci może być kosztowne:

Pattern pattern = Pattern.compile("b%s(?!w)".format(targetWord));

Pattern pattern = Pattern.compile("bwants(?!w)");
Matcher matcher = pattern.matcher(searchText);

int wordCount = 0;
while (matcher.find())
    wordCount++;

System.out.println(wordCount);

Powoduje to również:

2

Wzorzec wydajności

Więc który jest najbardziej wydajny? Przeprowadźmy mały test porównawczy:

int runs = 100000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    int result = countOccurencesWithSplit(searchText, targetWord);
}

long end1 = System.currentTimeMillis();
System.out.println(String.format("Array split approach took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
  for (int i = 0; i < runs; i++) {
    int result = countOccurencesWithCollections(searchText, targetWord);
}

long end2 = System.currentTimeMillis();
System.out.println(String.format("Collections.frequency() approach took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    int result = countOccurencesWithRegex(searchText, targetWord);
}

long end3 = System.currentTimeMillis();
System.out.println(String.format("Regex approach took: %s miliseconds", end3-start3));

Każda metoda zostanie uruchomiona 100000 razy (im wyższa liczba, tym mniejsza wariancja i wyniki losowe, ze względu na prawo dużych liczb). Uruchomienie tego kodu powoduje:

Array split approach took: 152 miliseconds
Collections.frequency() approach took: 140 miliseconds
Regex approach took: 92 miliseconds

Jednak – co się stanie, jeśli sprawimy, że wyszukiwanie będzie droższe obliczeniowo, zwiększając je? Wygenerujmy zdanie syntetyczne:

List possibleWords = Arrays.asList("hello", "world ");
StringBuffer searchTextBuffer = new StringBuffer();

for (int i = 0; i < 100; i++) {
    searchTextBuffer.append(String.join(" ", possibleWords));
}
System.out.println(searchTextBuffer);

To tworzy ciąg z zawartością:

hello world hello world hello world hello ...

Teraz, gdybyśmy mieli szukać „hello” lub „world” – byłoby znacznie więcej dopasowań niż dwa poprzednie. Jak nasze metody radzą sobie teraz w benchmarku?

Array split approach took: 606 miliseconds
Collections.frequency() approach took: 899 miliseconds
Regex approach took: 801 miliseconds

Teraz dzielenie tablicy jest najszybsze! Ogólnie rzecz biorąc, testy porównawcze zależą od różnych czynników – takich jak przestrzeń wyszukiwania, słowo docelowe itp., a Twój osobisty przypadek użycia może różnić się od testu porównawczego.

Rada: Wypróbuj metody na własnym tekście, zanotuj godziny i wybierz dla siebie najbardziej wydajną i elegancką.

Wnioski

W tym krótkim przewodniku przyjrzeliśmy się, jak zliczać wystąpienia słów dla słowa docelowego w ciągu znaków w Javie. Zaczęliśmy od podzielenia łańcucha i użycia prostego licznika, a następnie użycia Collections klasa pomocnicza, a na koniec przy użyciu wyrażeń regularnych.

Na koniec przeprowadziliśmy testy porównawcze metod i zauważyliśmy, że wydajność nie jest liniowa i zależy od przestrzeni wyszukiwania. W przypadku dłuższych tekstów wejściowych z wieloma dopasowaniami najskuteczniejsze wydaje się dzielenie tablic. Wypróbuj wszystkie trzy metody samodzielnie i wybierz najbardziej skuteczną.