Java: Szavak előfordulásának számlálása a karakterláncban

Bevezetés

Egy karakterláncban előforduló szavak számának megszámlálása meglehetősen egyszerű feladat, de ennek többféle megközelítése is van. Számolni kell a módszer hatékonyságával is, hiszen általában akkor érdemes automatizált eszközöket alkalmazni, ha nem akarunk kézi munkát végezni – vagyis ha nagy a keresési tér.

Ebből az útmutatóból megtudhatja, hogyan kell megszámolni a szóelőfordulások számát egy karakterláncban Java nyelven:

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

Megkeressük az előfordulások számát targetWord, Felhasználva String.split(), Collections.frequency() és reguláris kifejezések.

Számolja meg a szóelőfordulásokat a karakterláncban ezzel String.split()

A legegyszerűbb módja annak, hogy megszámoljuk egy célszó előfordulását egy karakterláncban, ha felosztjuk a karakterláncot minden szónál, és a tömbön keresztül ismételjük, növelve a wordCount minden meccsen. Vegye figyelembe, hogy ha egy szó körül bármilyen írásjel van, mint pl wants. a mondat végén – az egyszerű szószintű tagolás helyesen kezeli wants és a wants. külön szavakként!

Ennek megkerüléséhez egyszerűen eltávolíthat minden írásjelet a mondatból előtt felosztása:

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);

A for ciklusban, egyszerűen áthaladunk a tömbön, és ellenőrizzük, hogy az egyes indexeknél az elem egyenlő-e a targetWord. Ha igen, akkor növeljük a wordCount, amely a végrehajtás végén a következőt írja ki:

2

Számolja meg a szóelőfordulásokat a karakterláncban ezzel Collections.frequency()

A Collections.frequency() módszer sokkal tisztább, magasabb szintű megvalósítást biztosít, amely elvonatkoztat egy egyszerűt for hurok, és ellenőrzi mindkét azonosságot (akár objektum is másik objektum) és egyenlőség (egy tárgy egyenlő-e egy másik tárggyal, az adott tárgy minőségi jellemzőitől függően).

A frequency() metódus elfogad egy listát a kereséshez, és a célobjektumot, és működik minden más objektumnál is, ahol a viselkedés attól függ, hogy az objektum hogyan valósítja meg equals(). A húrok esetében equals() ellenőrzi a a karakterlánc tartalma:

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

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

Itt konvertáltuk a kapott tömböt split() egy Java-ba ArrayList, a segítő segítségével asList() módszer a Arrays osztály. A redukciós művelet frequency() egy egész számot ad vissza, amely a gyakoriságát jelöli targetWord a listában, és az eredmény:

2

Szóelőfordulások a karakterláncban -val Egyező (reguláris kifejezések – reguláris kifejezés)

Végül a Reguláris kifejezések segítségével kereshet mintákat, és megszámolhatja az egyező minták számát. A reguláris kifejezések erre készültek, így ez nagyon természetes illeszkedés a feladathoz. Java nyelven a Pattern osztály a reguláris kifejezések ábrázolására és fordítására szolgál, és a Matcher osztályt használják a minták megtalálására és egyeztetésére.

A RegEx használatával az írásjelek invarianciáját magába a kifejezésbe tudjuk kódolni, így nincs szükség a karakterlánc külső formázására vagy az írásjelek eltávolítására, ami előnyösebb nagy szövegeknél, ahol egy másik módosított változat tárolása a memóriában exponenciális lehet:

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);

Ez a következőket is eredményezi:

2

Hatékonysági referenciaérték

Tehát melyik a leghatékonyabb? Futtassunk egy kis benchmarkot:

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));

Mindegyik metódus 100000 XNUMX-szer fut le (minél nagyobb a szám, annál kisebb a szórás és az eredmények a véletlenek miatt, a nagy számok törvénye miatt). A kód futtatása a következőket eredményezi:

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

Azonban – mi történik, ha a keresést számításilag drágábbá tesszük azzal, hogy megnöveljük? Hozzunk létre egy szintetikus mondatot:

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);

Ezzel létrehoz egy karakterláncot a következő tartalommal:

hello world hello world hello world hello ...

Nos, ha a „hello” vagy a „world” kifejezésre keresnénk, sokkal több egyezés lenne, mint az előző kettő. Hogyan teljesítenek a módszereink most a benchmarkban?

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

Most a tömbfelosztás jön ki a leggyorsabban! Általánosságban elmondható, hogy a benchmarkok számos tényezőtől függenek – például a keresési területtől, a célszótól stb., és az Ön személyes használati esete eltérhet a referenciaértéktől.

Útmutatás: Próbálja ki a módszereket saját szövegén, jegyezze fel az időpontokat, és válassza ki az Ön számára leghatékonyabb és legelegánsabbat.

Következtetés

Ebben a rövid útmutatóban megvizsgáltuk, hogyan kell megszámolni a szóelőfordulásokat a célszóhoz egy karakterláncban Java nyelven. Kezdtük a karakterlánc felosztásával és egy egyszerű számláló használatával, majd a Collections segítő osztály, és végül a reguláris kifejezések használatával.

Végül összehasonlítottuk a módszereket, és megállapítottuk, hogy a teljesítmény nem lineáris, és a keresési tértől függ. Hosszabb, sok egyezést tartalmazó beviteli szövegeknél a tömbök felosztása tűnik a legeredményesebbnek. Próbálja ki mindhárom módszert egyedül, és válassza ki a leghatékonyabbat.