如何使用 binarysearch 加强 java 文本文件搜索？

Question

我正在尝试制作一个小应用程序，它可以在文本文件中进行搜索并识别其中使用的语言（首先是英语和土耳其语）。为此，我正在搜索字母 "k" 的字节外观。根据一些研究，这个字母在土耳其语中被广泛使用，在英语中使用得很少，并且具有相同的字节数。然而，问题是用我的代码在 110k 个字母的文本中找到字母 k 的出现需要大约 20 秒（或者对于 i7 7700hq comp 可能需要更多时间），所以这对我来说是个大问题，因为我正计划运行此代码超过 1k 个文本文件。我应该使用 java 的另一种方法进行搜索还是这是最快的方法？

提前致谢

我的代码是：

package deneme;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class deneme {
    public static int howmany =0;
    public static double ratio;
    public static void main(String args[]) throws IOException{

        File file = new File("c:\tr1.srt");
          byte[] bytesArray = new byte[(int) file.length()]; 

          FileInputStream fis = new FileInputStream(file);
          fis.read(bytesArray); //read file into bytes[]
          fis.close();
          byte searchVal = 107; // 'k' letter in byte code

          for(byte textbytes:bytesArray){
              Arrays.sort(bytesArray);
              int retVal = Arrays.binarySearch(bytesArray,0,bytesArray.length,searchVal);
              if(retVal >-1){
                  bytesArray[retVal]=0;
                  howmany++;
              }
          }
          System.out.println("Character \"k\" appears " + howmany +" times in the text");
          ratio = (double)howmany/(double)bytesArray.length;
          System.out.println("How many: "+howmany);
          System.out.println("Length: "+bytesArray.length);
          System.out.println("Ratio: "+ratio);
          if(ratio<0.01){
              System.out.println("Text file is probably not turkish");
          }else{
              System.out.println("Text file is probably turkish");
          }
    }
}

Answer 1

排序是一项代价高昂的操作。而且您正在为每个字符对数组进行排序，这是低效的。相反，您可以按顺序遍历所有字符一次，如果该特定字符是 'k'，则只需递增计数器。这是一个示例代码

for(byte textBytes: bytesArray) {
    if(textBytes == searchVal) {
        howmany++;
    }
}

用这个 for 循环代替你的。你应该更快地得到结果。

Answer 2

排序会访问每个字节，因此您不需要排序，只需访问每个字节一次。

如果你这样做，你实际上可以计算所有字节的频率：

int[] freqs = new int[256];
for(byte b: bytearray)
   freqs[b&0x0ff]++;

然后只需查找您喜欢的字节，如 freqs['k']+freqs['K'].

此外，您可以只在文件输入流上打开一个缓冲输入流，并避免使用巨大的字节 []，只需遍历 bufferedinputstream.read()（这是一个 int 0..255）并在 -1 时停止.

Answer 3

首先，如果您使用字母，请使用 Reader，而不是 InputStream：

Reader reader = new BufferedReader(new FileReader(file));

接下来，你实现的计算字母'k'的方法是……怎么说呢……很有创意。只要找到，您就可以多次二进制搜索 'k' 。虽然这有效，但远非最佳。我认为它是 O(n*log n) 而它很容易在 O(n) 中通过一次读取字符解决。沿线的东西：

private static final char CHAR_k = 'k';
// ...
int count_k = 0;
int r;
while ((r = reader.read()) != -1) {
    char ch = (char) r;
    if (ch == CHAR_k) {
        count_k++
    }
}

如何使用 binarysearch 加强 java 文本文件搜索？

How can i fasten java text file search with binarysearch?

java

arrays

character-encoding

binary-search