So führen Sie eine binäre Suche einer Textdatei durch

Question

Ich habe eine große Textdatei (5Mb), die ich in meiner Android-Anwendung verwende. Ich erstelle die Datei als eine Liste vorsortierter Strings, und die Datei ändert sich nicht, sobald sie erstellt wurde. Wie kann ich eine binäre Suche nach dem Inhalt dieser Datei durchführen, ohne Zeile für Zeile zu lesen, um den passenden String zu finden?

Answer 1

Da sich der Inhalt der Datei nicht ändert, können Sie die Datei in mehrere Teile aufteilen. Sagen Sie A-G, H-N, 0-T und U-Z. Dadurch können Sie das erste Zeichen überprüfen und sofort die mögliche Menge auf ein Viertel der ursprünglichen Größe reduzieren. Jetzt wird eine lineare Suche nicht so lange dauern oder das Lesen der ganzen Datei könnte eine Option sein. Dieser Prozess könnte erweitert werden, wenn n/4 immer noch zu groß ist, aber die Idee ist die gleiche. Erstellen Sie die Suchaufschlüsselungen in der Dateistruktur, anstatt alles im Speicher zu tun.

Answer 2

Eine Datei von 5 MB ist nicht so groß - Sie sollten in der Lage sein, jede Zeile in ein String[] Array zu lesen, das Sie dann java.util.Arrays.binarySearch() verwenden können, um die gewünschte Zeile zu finden. Dies ist meine empfohlene Vorgehensweise.

Wenn Sie nicht die ganze Datei in Ihrer App lesen möchten, wird es komplizierter. Wenn jede Zeile der Datei die gleiche Länge ist, und die Datei bereits sortiert, dann können Sie die Datei in Random öffnen und einer binären Suche selbst durchführen, indem seek() wie dies mit ...

// 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 

Wenn jedoch Die Datei hat keine Zeilen mit fester Breite. Dann können Sie eine Binärsuche nicht einfach durchführen, ohne sie zuerst in den Speicher zu laden, da Sie nicht wie bei Linien mit fester Breite schnell zu einer bestimmten Zeile in der Datei springen können .

Answer 3

In einer Textdatei mit einheitlicher Zeichenlänge können Sie in der Mitte des fraglichen Intervalls zeichenweise suchen, beginnen, Zeichen zu lesen, bis Sie den Begrenzer treffen, und dann die nachfolgende Zeichenfolge als Näherung für die elementweise Mitte verwenden. Das Problem damit, dies bei Android zu tun, ist jedoch, dass Sie nicht können get random access to a resource (obwohl ich nehme an, Sie könnten es einfach jedes Mal wieder öffnen). Außerdem verallgemeinert diese Technik nicht Karten und Sätze anderer Typen. Eine andere Möglichkeit wäre, mit einem RandomAccessFile ein "Array" von Ints - eines für jeden String - am Anfang der Datei zu schreiben, dann zurückzugehen und sie mit den Positionen ihrer entsprechenden Strings zu aktualisieren. Wiederum muss die Suche herumspringen.

Was ich tun würde (und in meiner eigenen App gemacht habe), ist eine hash set in einer Datei zu implementieren. Dieser trennt Kette mit Bäumen.

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

} 

Ein Testprogramm

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

Lassen Sie sich bei pass a Context es brauchen, ob und wann Sie es für Android ändern, so dass es die GetResources zugreifen können() -Methode.

Sie werden wahrscheinlich auch stop the android build tools from compressing the file wollen, was anscheinend nur getan werden kann - wenn Sie mit der GUI arbeiten - indem Sie die Dateierweiterung in etwas wie jpg ändern. Dies machte den Prozess in meiner App 100 bis 300 Mal schneller.

Sie könnten auch in giving yourself more memory mit der NDK suchen.

Answer 4

Hier ist etwas, was ich schnell zusammengestellt habe. Es verwendet zwei Dateien, eine mit den Wörtern, die andere mit den Offsets.Das Format der Offset-Datei ist dies: die ersten 10 Bits enthalten die Wortgröße, die letzten 22 Bits enthalten den Offset (die Wortposition, zum Beispiel wäre aaah 0, die abstossbare wäre 4 usw.). Es ist in Big-Endian (Java-Standard) kodiert. Hoffe es hilft jemandem.

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 _`___`_$___/_`_> 

ich diese Dateien in C# erstellt, aber hier ist der Code für sie (es verwendet eine TXT-Datei mit Wörter getrennt durch 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++; 
      } 
     } 
    } 
} 

Und dies ist der Java-Code für die Binärdatei Suche:

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

Obwohl es wie übertrieben klingen mag, speichern keine Daten, die Sie brauchen diese als Textdatei mit zu tun. Erstellen Sie eine Datenbank und fragen Sie die Daten in der Datenbank ab. Dies sollte sowohl effektiv als auch schnell sein.