テキストファイルのバイナリ検索を行う方法

Question

私はAndroidアプリケーションで使用する大きなテキストファイル（5Mb）を持っています。私はあらかじめソートされたストリングのリストとしてファイルを作成し、ファイルは作成されても変更されません。このファイルの内容をバイナリ検索するには、行ごとに一致する文字列を検索することなく、どうすればよいですか？

Answer 1

ファイルの内容は変更されないため、ファイルを複数に分割することができます。 A-G、H-N、0-T、U-Zと言う。これにより、最初の文字を確認し、直ちに元のサイズの4分の1に設定することができます。線形検索では時間がかかりませんし、ファイル全体を読むこともオプションになります。このプロセスは、n/4が依然として大きければ拡張できますが、アイデアは同じです。検索構造をメモリ内ですべて実行するのではなく、ファイル構造に組み込みます。

Answer 2

5MBのファイルはそれほど大きくありません。String[]アレイに各行を読み込むことができます。java.util.Arrays.binarySearch()を使用して、必要な行を見つけることができます。これが私の推奨するアプローチです。

ファイル全体をアプリに読み込みたくない場合は、もっと複雑になります。ファイルの各行が同じ長さであり、ファイルがすでにソートされている場合は、場合、しかし...

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

をのRandomAccessFileでファイルを開いて、このようなseek()を使用してバイナリ検索を自分で行うことができますファイルに固定幅の行がない場合、固定幅の行でできるように、ファイル内の特定の行に素早くジャンプできないため、バイナリ検索をメモリにロードせずに簡単に実行することはできません。

Answer 3

文字の長さの中間のテキストファイルでは、問題の文字の間隔の中間に移動して、区切り文字を叩くまで文字の読み取りを開始し、その後の文字列を要素の賢明な中間の近似値として使用します。しかし、アンドロイドでこれを行う問題は明らかにあなたがget random access to a resource（私はあなたが毎回それを再オープンすることができたと思うが）できないということです。さらに、この手法はマップや他のタイプのセットには一般化されません。

別のオプションは、ファイルの先頭にあるintの "配列"（各文字列ごとに1つ）を書き込んでから、対応するStringの位置でそれらを更新することです。再度検索するにはジャンプが必要です。

私がやりたいことは（自分のアプリでやった）hash setをファイルに実装しています。これは木々と鎖を分離します。

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

} 

テストプログラム

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

またあれば、いつそれがgetResources（）メソッドにアクセスすることができますので、あなたは、アンドロイドのためにそれを修正し、それにpass a Contextする必要があります。

また、stop the android build tools from compressing the fileにしたいと思うかもしれません。これは、GUIを使って作業している場合は、ファイルの拡張子をjpgなどに変更するだけで可能です。これにより、私のアプリで約100〜300倍速くなりました。

また、を使用してgiving yourself more memoryを調べることもできます。

Answer 4

ここに私はすぐにまとめるものがあります。 2つのファイルを使用します.1つは単語、もう1つはオフセットです。オフセットファイルのフォーマットは次のとおりです。最初の10ビットはワードサイズを含み、最後の22ビットはオフセットを含みます（たとえば、aaahは0、abasementableは4などです）。ビッグエンディアンでエンコードされています（Java標準）。誰かを助けることを願っています。

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

私はC＃でこれらのファイルを作成したが、ここではそのためのコードだ（それはとtxtファイルを使用しています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++; 
      } 
     } 
    } 
} 

そしてこれは、バイナリファイル検索のためのJavaコードである：それはやり過ぎのように聞こえるかもしれないが

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

、フラット・ファイルなどでこれを行うために必要なデータを格納しないでください。データベースを作成し、データベース内のデータを照会します。これは効果的で速くなければなりません。