Jak wykonać wyszukiwanie binarne pliku tekstowego

Question

Mam duży plik tekstowy (5 MB), którego używam w mojej aplikacji na Androida. Tworzę plik jako listę wstępnie posortowanych ciągów, a plik nie zmienia się po utworzeniu. Jak mogę przeprowadzić wyszukiwanie binarne na zawartości tego pliku, bez czytania linii po linii, aby znaleźć pasujący ciąg?

Answer 1

Ponieważ treść pliku się nie zmienia, można podzielić plik na kilka części. Powiedz A-G, H-N, 0-T i U-Z. Umożliwia to sprawdzenie pierwszego znaku i natychmiastowe obcięcie możliwego zestawu do czwartego rozmiaru oryginału. Teraz wyszukiwanie liniowe nie potrwa długo, a czytanie całego pliku może być opcją. Proces ten można rozszerzyć, jeśli n/4 jest wciąż zbyt duży, ale idea jest taka sama. Zbuduj podział wyszukiwania na strukturę plików, zamiast próbować zrobić to wszystko w pamięci.

Answer 2

Plik 5 MB nie jest zbyt duży - powinieneś być w stanie odczytać każdą linię w tablicy String[], którą możesz następnie użyć java.util.Arrays.binarySearch(), aby znaleźć żądaną linię. To jest moje zalecane podejście.

Jeśli nie chcesz czytać całego pliku w aplikacji, staje się on bardziej skomplikowany. Jeśli każdy wiersz pliku jest taka sama długość, a plik jest już posortowane, można otworzyć plik w RandomAccessFile i przeprowadzić przeszukiwanie binarne ciała za pomocą seek() takiego ...

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

Jednakże, jeśli plik nie ma linii o stałej szerokości, wtedy nie można łatwo wykonać wyszukiwania binarnego bez wcześniejszego załadowania go do pamięci, ponieważ nie można szybko przeskoczyć do konkretnej linii w pliku, jak to możliwe za pomocą linii o stałej szerokości .

Answer 3

W jednolitym pliku tekstowym o długości znaku można wyszukiwać w połowie przedziałów, o których mowa, znaków, zaczynać czytanie znaków, aż trafisz swojego deliminatora, a następnie użyj kolejnego ciągu jako przybliżenia dla elementu mądry środek. Problem z zrobieniem tego na Androidzie jest jednak prawdopodobnie nie można get random access to a resource (choć przypuszczam, że można go ponownie otworzyć za każdym razem). Ponadto technika ta nie jest generalizowana na mapy i zestawy innych typów.

Inną opcją byłoby (używając RandomAccessFile) napisać "tablicę" ints - po jednym dla każdego ciągu - na początku pliku, a następnie wrócić i zaktualizować je lokalizacjami ich odpowiednich ciągów. Znowu poszukiwania będą wymagały skakania.

Co mogę zrobić (i zrobiłem w mojej własnej aplikacji) jest implementacja hash set w pliku. Ten oddziela łańcuchy od drzew.

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

} 

Program testowy

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

Trzeba także do pass a Context do tego, czy i kiedy ją zmodyfikować dla Androida, dzięki czemu może uzyskać dostęp do getResources metoda().

Prawdopodobnie będziesz również chciał stop the android build tools from compressing the file, który najwyraźniej można zrobić tylko - jeśli pracujesz z GUI - zmieniając rozszerzenie pliku na takie, jak jpg. W mojej aplikacji proces ten był około 100 do 300 razy szybszy.

Możesz także zajrzeć do giving yourself more memory, korzystając z NDK.

Answer 4

Oto coś, co szybko złożyłem razem. Używa dwóch plików, jednego ze słowami, a drugiego z przesunięciami.Format pliku z przesunięciem jest następujący: pierwsze 10 bitów zawiera rozmiar słowa, ostatnie 22 bity zawierają przesunięcie (pozycja słowa, na przykład aaah wynosiłaby 0, zmienne 4, itd.). Jest kodowany w big endian (standard Java). Mam nadzieję, że to pomaga komuś.

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

stworzyłem te pliki w C#, ale tutaj jest kod dla niego (używa pliku txt z słowa oddzielone przez 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++; 
      } 
     } 
    } 
} 

I to jest kod Java do wyszukiwania plików binarnych:

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

Choć może to wydawać się przesadą, nie przechowywać dane trzeba to zrobić z postaci pliku płaskiego. Utwórz bazę danych i przeszukuj dane w bazie danych. Powinno to być zarówno skuteczne, jak i szybkie.