Java: Đếm số lượng từ xuất hiện trong chuỗi

Giới thiệu

Đếm số lần xuất hiện từ trong một chuỗi là một nhiệm vụ khá dễ dàng, nhưng có một số phương pháp để làm như vậy. Bạn cũng phải tính đến hiệu quả của phương pháp, vì bạn thường muốn sử dụng các công cụ tự động khi bạn không muốn thực hiện lao động thủ công - tức là khi không gian tìm kiếm lớn.

Trong hướng dẫn này, bạn sẽ học cách đếm số lần xuất hiện từ trong một chuỗi trong Java:

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

Chúng tôi sẽ tìm kiếm số lần xuất hiện của targetWord, Sử dụng String.split(), Collections.frequency() và Biểu thức chính quy.

Đếm số lần xuất hiện từ trong chuỗi với String.split ()

Cách đơn giản nhất để đếm số lần xuất hiện của một từ đích trong một chuỗi là tách chuỗi trên mỗi từ và lặp lại qua mảng, tăng dần a wordCount trên mỗi trận đấu. Lưu ý rằng khi một từ có bất kỳ loại dấu câu nào xung quanh nó, chẳng hạn như wants. ở cuối câu - sự phân chia cấp độ từ đơn giản sẽ xử lý chính xác wants và wants. như những từ riêng biệt!

Để giải quyết vấn đề này, bạn có thể dễ dàng xóa tất cả các dấu câu khỏi câu trước tách nó ra:

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

Trong tạp chí for vòng lặp, chúng tôi chỉ cần lặp lại qua mảng, kiểm tra xem phần tử ở mỗi chỉ mục có bằng targetWord. Nếu có, chúng tôi tăng wordCount, ở cuối quá trình thực thi, sẽ in:

2

Đếm số lần xuất hiện từ trong chuỗi với Collections.frequency ()

Sản phẩm Collections.frequency() phương pháp này cung cấp một triển khai cấp cao hơn, rõ ràng hơn nhiều, giúp loại bỏ một cách đơn giản for vòng lặp và kiểm tra cả danh tính (liệu một đối tượng is đối tượng khác) và bình đẳng (một đối tượng có bằng với đối tượng khác hay không, phụ thuộc vào các đặc điểm chất lượng của đối tượng đó).

Sản phẩm frequency() phương thức chấp nhận một danh sách để tìm kiếm và đối tượng đích, cũng như hoạt động cho tất cả các đối tượng khác, trong đó hành vi phụ thuộc vào cách đối tượng tự triển khai equals(). Trong trường hợp chuỗi, equals() kiểm tra nội dung của chuỗi:

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

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

Ở đây, chúng tôi đã chuyển đổi mảng thu được từ split() thành một Java ArrayList, sử dụng trình trợ giúp asList() phương pháp của Arrays lớp. Hoạt động giảm frequency() trả về một số nguyên biểu thị tần suất của targetWord trong danh sách và kết quả là:

2

Từ xảy ra trong chuỗi với Matcher (Biểu thức chính quy - RegEx)

Cuối cùng, bạn có thể sử dụng Biểu thức chính quy để tìm kiếm các mẫu và đếm số lượng các mẫu phù hợp. Biểu thức chính quy được tạo ra cho điều này, vì vậy nó rất phù hợp tự nhiên cho nhiệm vụ. Trong Java, Pattern lớp được sử dụng để biểu diễn và biên dịch Biểu thức chính quy, và Matcher lớp được sử dụng để tìm và kết hợp các mẫu.

Sử dụng RegEx, chúng tôi có thể mã hóa bất biến dấu câu vào chính biểu thức, vì vậy không cần phải định dạng bên ngoài chuỗi hoặc xóa dấu câu, điều này thích hợp cho các văn bản lớn, nơi lưu trữ một phiên bản đã thay đổi khác trong bộ nhớ có thể tốn kém:

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

Điều này cũng dẫn đến:

2

Điểm chuẩn hiệu quả

Vì vậy, đó là hiệu quả nhất? Hãy chạy một điểm chuẩn nhỏ:

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

Mỗi phương pháp sẽ được chạy 100000 lần (số càng cao thì phương sai càng giảm và kết quả do may rủi, do quy luật số lớn). Chạy mã này dẫn đến:

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

Tuy nhiên - điều gì sẽ xảy ra nếu chúng ta làm cho việc tìm kiếm trở nên tốn kém hơn về mặt tính toán bằng cách làm cho nó lớn hơn? Hãy tạo một câu tổng hợp:

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

Thao tác này tạo một chuỗi có nội dung:

hello world hello world hello world hello ...

Bây giờ, nếu chúng ta tìm kiếm “xin chào” hoặc “thế giới” - sẽ có nhiều kết quả phù hợp hơn so với hai từ trước đó. Làm thế nào để các phương pháp của chúng tôi hoạt động bây giờ trong điểm chuẩn?

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

Giờ đây, tính năng tách mảng diễn ra nhanh nhất! Nói chung, điểm chuẩn phụ thuộc vào nhiều yếu tố khác nhau - chẳng hạn như không gian tìm kiếm, từ mục tiêu, v.v. và trường hợp sử dụng cá nhân của bạn có thể khác với điểm chuẩn.

Khuyên bảo: Hãy thử các phương pháp trên văn bản của riêng bạn, ghi lại thời gian và chọn phương pháp hiệu quả và thanh lịch nhất cho bạn.

Kết luận

Trong hướng dẫn ngắn này, chúng ta đã xem xét cách đếm số lần xuất hiện của từ cho một từ đích, trong một chuỗi trong Java. Chúng tôi đã bắt đầu bằng cách tách chuỗi và sử dụng một bộ đếm đơn giản, tiếp theo là sử dụng Collections lớp trợ giúp và cuối cùng là sử dụng Biểu thức chính quy.

Cuối cùng, chúng tôi đã đánh giá chuẩn các phương pháp và lưu ý rằng hiệu suất không tuyến tính và phụ thuộc vào không gian tìm kiếm. Đối với các văn bản đầu vào dài hơn với nhiều kết quả khớp, việc tách mảng có vẻ là hoạt động hiệu quả nhất. Hãy tự mình thử cả ba phương pháp và chọn một phương pháp hiệu quả nhất.