Cách thực hiện tìm kiếm nhị phân của tệp văn bản

Question

Tôi có tệp văn bản lớn (5Mb) mà tôi sử dụng trong ứng dụng Android của mình. Tôi tạo ra các tập tin như là một danh sách các chuỗi được sắp xếp trước, và các tập tin không thay đổi một khi nó được tạo ra. Làm thế nào tôi có thể thực hiện tìm kiếm nhị phân trên nội dung của tệp này, mà không đọc từng dòng để tìm Chuỗi phù hợp?

Answer 1

Vì nội dung của tệp không thay đổi, bạn có thể chia tệp thành nhiều phần. Nói A-G, H-N, 0-T và U-Z. Điều này cho phép bạn kiểm tra ký tự đầu tiên và ngay lập tức có thể cắt tập hợp có thể thành một phần tư kích thước ban đầu. Bây giờ tìm kiếm tuyến tính sẽ không mất nhiều thời gian hoặc đọc toàn bộ tệp có thể là một tùy chọn. Quá trình này có thể được mở rộng nếu n/4 vẫn còn quá lớn, nhưng ý tưởng là như nhau. Xây dựng phân tích tìm kiếm vào cấu trúc tệp thay vì cố gắng thực hiện tất cả trong bộ nhớ.

Answer 2

Tệp 5MB không lớn lắm - bạn sẽ có thể đọc từng dòng vào một mảng String[], sau đó bạn có thể sử dụng java.util.Arrays.binarySearch() để tìm dòng bạn muốn. Đây là cách tiếp cận được đề nghị của tôi.

Nếu bạn không muốn đọc toàn bộ tệp trong ứng dụng của mình, thì sẽ phức tạp hơn. Nếu mỗi dòng của tập tin là chiều dài tương tự, và các tập tin đã được sắp xếp, sau đó bạn có thể mở tập tin trong RandomAccessFile và thực hiện tìm kiếm nhị phân chính mình bằng cách sử dụng seek() như thế này ...

// open the file for reading 
RandomAccessFile raf = new RandomAccessFile("myfile.txt","r"); 
String searchValue = "myline"; 
int lineSize = 50; 
int numberOfLines = raf.length()/lineSize; 

// perform the binary search... 
byte[] lineBuffer = new byte[lineSize]; 
int bottom = 0; 
int top = numberOfLines; 
int middle; 
while (bottom <= top){ 
    middle = (bottom+top)/2; 
    raf.seek(middle*lineSize); // jump to this line in the file 
    raf.read(lineBuffer); // read the line from the file 
    String line = new String(lineBuffer); // convert the line to a String 

    int comparison = line.compareTo(searchValue); 
    if (comparison == 0){ 
    // found it 
    break; 
    } 
    else if (comparison < 0){ 
    // line comes before searchValue 
    bottom = middle + 1; 
    } 
    else { 
    // line comes after searchValue 
    top = middle - 1; 
    } 
    } 

raf.close(); // close the file when you're finished 

Tuy nhiên, nếu tệp không có các đường có chiều rộng cố định, sau đó bạn không thể dễ dàng thực hiện tìm kiếm nhị phân mà không tải nó vào bộ nhớ trước, vì bạn không thể nhanh chóng chuyển đến một dòng cụ thể trong tệp như bạn có thể với các đường có chiều rộng cố định .

Answer 3

Trong tệp văn bản có độ dài ký tự đồng nhất, bạn có thể tìm đến giữa khoảng thời gian trong ký tự câu hỏi, bắt đầu đọc ký tự cho đến khi bạn nhấn dấu phân cách của mình, sau đó sử dụng chuỗi tiếp theo làm xấp xỉ cho phần tử chính giữa. Tuy nhiên, vấn đề khi làm điều này trong Android là dường như bạn không thể get random access to a resource (mặc dù tôi cho rằng bạn chỉ có thể mở lại nó mọi lúc). Hơn nữa kỹ thuật này không tổng quát hóa các bản đồ và các loại khác.

Một tùy chọn khác sẽ là (sử dụng RandomAccessFile) viết một "mảng" của ints - một cho mỗi chuỗi - ở đầu tệp rồi quay lại và cập nhật chúng với vị trí của chuỗi tương ứng của chúng. Một lần nữa tìm kiếm sẽ yêu cầu nhảy xung quanh.

Điều tôi sẽ làm (và thực hiện trong ứng dụng của riêng mình) là triển khai hash set trong một tệp. Cái này tách riêng với cây.

import java.io.BufferedInputStream; 
import java.io.DataInputStream; 
import java.io.File; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.io.RandomAccessFile; 
import java.util.ArrayList; 
import java.util.Collections; 
import java.util.LinkedList; 
import java.util.Set; 

class StringFileSet { 

    private static final double loadFactor = 0.75; 

    public static void makeFile(String fileName, String comment, Set<String> set) throws IOException { 
     new File(fileName).delete(); 
     RandomAccessFile fout = new RandomAccessFile(fileName, "rw"); 

     //Write comment 
     fout.writeUTF(comment); 

     //Make bucket array 
     int numBuckets = (int)(set.size()/loadFactor); 

     ArrayList<ArrayList<String>> bucketArray = new ArrayList<ArrayList<String>>(numBuckets); 
     for (int ii = 0; ii < numBuckets; ii++){ 
      bucketArray.add(new ArrayList<String>()); 
     } 

     for (String key : set){ 
      bucketArray.get(Math.abs(key.hashCode()%numBuckets)).add(key); 
     } 

     //Sort key lists in preparation for creating trees 
     for (ArrayList<String> keyList : bucketArray){ 
      Collections.sort(keyList); 
     } 

     //Make queues in preparation for creating trees 
     class NodeInfo{ 

      public final int lower; 
      public final int upper; 
      public final long callingOffset; 

      public NodeInfo(int lower, int upper, long callingOffset){ 
       this.lower = lower; 
       this.upper = upper; 
       this.callingOffset = callingOffset; 
      } 

     } 

     ArrayList<LinkedList<NodeInfo>> queueList = new ArrayList<LinkedList<NodeInfo>>(numBuckets); 
     for (int ii = 0; ii < numBuckets; ii++){ 
      queueList.add(new LinkedList<NodeInfo>()); 
     } 

     //Write bucket array 
     fout.writeInt(numBuckets); 
     for (int index = 0; index < numBuckets; index++){ 
      queueList.get(index).add(new NodeInfo(0, bucketArray.get(index).size()-1, fout.getFilePointer())); 
      fout.writeInt(-1); 
     } 

     //Write trees 
     for (int bucketIndex = 0; bucketIndex < numBuckets; bucketIndex++){ 
      while (queueList.get(bucketIndex).size() != 0){ 
       NodeInfo nodeInfo = queueList.get(bucketIndex).poll(); 
       if (nodeInfo.lower <= nodeInfo.upper){ 
        //Set respective pointer in parent node 
        fout.seek(nodeInfo.callingOffset); 
        fout.writeInt((int)(fout.length() - (nodeInfo.callingOffset + 4))); //Distance instead of absolute position so that the get method can use a DataInputStream 
        fout.seek(fout.length()); 

        int middle = (nodeInfo.lower + nodeInfo.upper)/2; 

        //Key 
        fout.writeUTF(bucketArray.get(bucketIndex).get(middle)); 

        //Left child 
        queueList.get(bucketIndex).add(new NodeInfo(nodeInfo.lower, middle-1, fout.getFilePointer())); 
        fout.writeInt(-1); 

        //Right child 
        queueList.get(bucketIndex).add(new NodeInfo(middle+1, nodeInfo.upper, fout.getFilePointer())); 
        fout.writeInt(-1); 
       } 
      } 
     } 

     fout.close(); 
    } 

    private final String fileName; 
    private final int numBuckets; 
    private final int bucketArrayOffset; 

    public StringFileSet(String fileName) throws IOException { 
     this.fileName = fileName; 

     DataInputStream fin = new DataInputStream(new BufferedInputStream(new FileInputStream(fileName))); 

     short numBytes = fin.readShort(); 
     fin.skipBytes(numBytes); 
     this.numBuckets = fin.readInt(); 
     this.bucketArrayOffset = numBytes + 6; 

     fin.close(); 
    } 

    public boolean contains(String key) throws IOException { 
     boolean containsKey = false; 

     DataInputStream fin = new DataInputStream(new BufferedInputStream(new FileInputStream(this.fileName))); 

     fin.skipBytes(4*(Math.abs(key.hashCode()%this.numBuckets)) + this.bucketArrayOffset); 

     int distance = fin.readInt(); 
     while (distance != -1){ 
      fin.skipBytes(distance); 

      String candidate = fin.readUTF(); 
      if (key.compareTo(candidate) < 0){ 
       distance = fin.readInt(); 
      }else if (key.compareTo(candidate) > 0){ 
       fin.skipBytes(4); 
       distance = fin.readInt(); 
      }else{ 
       fin.skipBytes(8); 
       containsKey = true; 
       break; 
      } 
     } 

     fin.close(); 

     return containsKey; 
    } 

} 

Một chương trình thử nghiệm

import java.io.File; 
import java.io.IOException; 
import java.util.HashSet; 

class Test { 
    public static void main(String[] args) throws IOException { 
     HashSet<String> stringMemorySet = new HashSet<String>(); 

     stringMemorySet.add("red"); 
     stringMemorySet.add("yellow"); 
     stringMemorySet.add("blue"); 

     StringFileSet.makeFile("stringSet", "Provided under ... included in all copies and derivatives ...", stringMemorySet); 
     StringFileSet stringFileSet = new StringFileSet("stringSet"); 

     System.out.println("orange -> " + stringFileSet.contains("orange")); 
     System.out.println("red -> " + stringFileSet.contains("red")); 
     System.out.println("yellow -> " + stringFileSet.contains("yellow")); 
     System.out.println("blue -> " + stringFileSet.contains("blue")); 

     new File("stringSet").delete(); 

     System.out.println(); 
    } 
} 

Bạn cũng sẽ cần phải pass a Context với nó, nếu và khi bạn sửa đổi nó cho android, vì vậy nó có thể truy cập vào getResources() phương pháp.

Bạn cũng có thể sẽ muốn stop the android build tools from compressing the file, có vẻ như chỉ được thực hiện - nếu bạn đang làm việc với GUI - bằng cách thay đổi phần mở rộng của tệp thành một cái gì đó chẳng hạn như jpg. Điều này làm cho quy trình nhanh hơn trong khoảng 100 đến 300 lần trong ứng dụng của tôi.

Bạn cũng có thể xem xét giving yourself more memory bằng cách sử dụng NDK.

Answer 4

Đây là điều tôi đã nhanh chóng kết hợp với nhau. Nó sử dụng hai tập tin, một với các từ, một với các offset.Định dạng của tệp offset là: 10 bit đầu tiên chứa kích thước từ, 22 bit cuối cùng chứa bù đắp (vị trí từ, ví dụ, aaah sẽ là 0, có thể bỏ qua sẽ là 4, v.v.). Nó được mã hóa ở dạng cuối lớn (tiêu chuẩn java). Hy vọng nó sẽ giúp ai đó.

word.dat:

aaahabasementableabnormalabnormalityabortionistabortion-rightsabracadabra

wordx.dat:

00 80 00 00 01 20 00 04 00 80 00 0D 01 00 00 11 _____ __________ 
01 60 00 19 01 60 00 24 01 E0 00 2F 01 60 00 3E _`___`_$___/_`_> 

Tôi tạo ra những tập tin trong C#, nhưng đây là mã cho nó (nó sử dụng một file txt với các từ được phân cách bằng crlfs)

static void Main(string[] args) 
{ 
    const string fIn = @"C:\projects\droid\WriteFiles\input\allwords.txt"; 
    const string fwordxOut = @"C:\projects\droid\WriteFiles\output\wordx.dat"; 
    const string fWordOut = @"C:\projects\droid\WriteFiles\output\word.dat"; 

    int i = 0; 
    int offset = 0; 
    int j = 0; 
    var lines = File.ReadLines(fIn); 

    FileStream stream = new FileStream(fwordxOut, FileMode.Create, FileAccess.ReadWrite); 
    using (EndianBinaryWriter wwordxOut = new EndianBinaryWriter(EndianBitConverter.Big, stream)) 
    { 
     using (StreamWriter wWordOut = new StreamWriter(File.Open(fWordOut, FileMode.Create))) 
     { 
      foreach (var line in lines) 
      { 
       wWordOut.Write(line); 
       i = offset | ((int)line.Length << 22); //first 10 bits to the left is the word size 
       offset = offset + (int)line.Length; 
       wwordxOut.Write(i); 
       //if (j == 7) 
        // break; 
       j++; 
      } 
     } 
    } 
} 

Và đây là mã Java để tìm kiếm tệp nhị phân:

public static void binarySearch() { 
    String TAG = "TEST"; 
    String wordFilePath = Environment.getExternalStorageDirectory().getAbsolutePath() + "/word.dat"; 
    String wordxFilePath = Environment.getExternalStorageDirectory().getAbsolutePath() + "/wordx.dat"; 

    String target = "abracadabra"; 
    boolean targetFound = false; 
    int searchCount = 0; 

    try { 
     RandomAccessFile raf = new RandomAccessFile(wordxFilePath, "r"); 
     RandomAccessFile rafWord = new RandomAccessFile(wordFilePath, "r"); 
     long low = 0; 
     long high = (raf.length()/4) - 1; 
     int cur = 0; 
     long wordOffset = 0; 
     int len = 0; 

     while (high >= low) { 
      long mid = (low + high)/2; 
      raf.seek(mid * 4); 
      cur = raf.readInt(); 
      Log.v(TAG + "-cur", String.valueOf(cur)); 

      len = cur >> 22; //word length 

      cur = cur & 0x3FFFFF; //first 10 bits are 0 

      rafWord.seek(cur); 
      byte [] bytes = new byte[len]; 

      wordOffset = rafWord.read(bytes, 0, len); 
      Log.v(TAG + "-wordOffset", String.valueOf(wordOffset)); 

      searchCount++; 

      String str = new String(bytes); 

      Log.v(TAG, str); 

      if (target.compareTo(str) < 0) { 
       high = mid - 1; 
      } else if (target.compareTo(str) == 0) { 
       targetFound = true; 
       break; 
      } else { 
       low = mid + 1; 
      } 
     } 

     raf.close(); 
     rafWord.close(); 
    } catch (FileNotFoundException e) { 
     e.printStackTrace(); 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 

    if (targetFound == true) { 
     Log.v(TAG + "-found " , String.valueOf(searchCount)); 
    } else { 
     Log.v(TAG + "-not found " , String.valueOf(searchCount)); 
    } 

} 

Answer 5

Mặc dù có vẻ quá mức cần thiết, không lưu trữ dữ liệu bạn cần làm với tệp phẳng. Tạo một cơ sở dữ liệu và truy vấn dữ liệu trong cơ sở dữ liệu. Điều này sẽ có hiệu quả và nhanh chóng.