टेक्स्ट फ़ाइल की बाइनरी खोज कैसे करें

Question

मेरे पास एक बड़ी टेक्स्ट फ़ाइल (5 एमबी) है जिसका उपयोग मैं अपने एंड्रॉइड एप्लिकेशन में करता हूं। मैं फ़ाइल को प्री-सॉर्टेड स्ट्रिंग्स की सूची के रूप में बना देता हूं, और फ़ाइल बनने के बाद फ़ाइल नहीं बदली जाती है। मिलान करने वाली स्ट्रिंग को खोजने के लिए लाइन-दर-लाइन पढ़ने के बिना, मैं इस फ़ाइल की सामग्री पर बाइनरी खोज कैसे कर सकता हूं?

Answer 1

चूंकि फ़ाइल की सामग्री परिवर्तित नहीं होती है, इसलिए आप फ़ाइल को कई टुकड़ों में तोड़ सकते हैं। ए-जी, एच-एन, 0-टी और यू-जेड कहें। यह आपको पहले अक्षर की जांच करने की अनुमति देता है और तुरंत मूल आकार के चौथे हिस्से में संभावित सेट को काटने में सक्षम हो जाता है। अब एक रैखिक खोज लंबे समय तक नहीं लगेगी या पूरी फाइल पढ़ने में एक विकल्प हो सकता है। अगर एन/4 अभी भी बहुत बड़ा है, तो यह प्रक्रिया विस्तारित की जा सकती है, लेकिन विचार समान है। स्मृति में सभी को करने की कोशिश करने के बजाय फ़ाइल संरचना में खोज टूटने का निर्माण करें।

Answer 2

एक 5MB फ़ाइल कि बड़ा नहीं है - आप एक String[] सरणी, जिसे फिर आप java.util.Arrays.binarySearch() उपयोग कर सकते हैं लाइन आप चाहते हैं खोजने के लिए में प्रत्येक पंक्ति को पढ़ने के लिए सक्षम होना चाहिए। यह मेरा अनुशंसित दृष्टिकोण है।

यदि आप अपनी फ़ाइल में पूरी फ़ाइल को नहीं पढ़ना चाहते हैं, तो यह अधिक जटिल हो जाता है। फ़ाइल की प्रत्येक पंक्ति में एक ही लंबाई है, और फ़ाइल पहले से सॉर्ट हो जाता है, तो आप RandomAccessFile में फ़ाइल खोल सकते और seek() इस तरह का उपयोग करके एक द्विआधारी खोज अपने आप को प्रदर्शन ...

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

हालांकि, अगर फ़ाइल में निश्चित-चौड़ाई वाली रेखाएं नहीं हैं, फिर आप इसे स्मृति में पहले लोड किए बिना बाइनरी खोज आसानी से नहीं कर सकते हैं, क्योंकि आप फ़ाइल में किसी विशिष्ट पंक्ति पर त्वरित रूप से कूद नहीं सकते जैसे कि आप निश्चित-चौड़ाई वाली रेखाओं के साथ कर सकते हैं ।

Answer 3

एक समान वर्ण लंबाई टेक्स्ट फ़ाइल में आप प्रश्न चरित्र में अंतराल के बीच की तलाश कर सकते हैं, जब तक आप अपने डेलिमिनेटर को हिट नहीं करते तब तक अक्षरों को पढ़ना शुरू करें, फिर बाद के स्ट्रिंग को तत्व के मध्य के अनुमान के रूप में उपयोग करें। एंड्रॉइड में ऐसा करने में समस्या, हालांकि, आप स्पष्ट रूप से get random access to a resource नहीं कर सकते हैं (हालांकि मुझे लगता है कि आप इसे हर बार फिर से खोल सकते हैं)। इसके अलावा यह तकनीक अन्य प्रकार के मानचित्रों और सेटों को सामान्यीकृत नहीं करती है।

एक और विकल्प होगा (RandomAccessFile का उपयोग करके) एक "सरणी" चींटियों को लिखें - प्रत्येक स्ट्रिंग के लिए - फ़ाइल की शुरुआत में फिर वापस जाएं और उन्हें उनके संबंधित स्ट्रिंग्स के स्थानों के साथ अपडेट करें। फिर खोज के आसपास कूदने की आवश्यकता होगी।

मैं क्या करूंगा (और अपने स्वयं के ऐप में किया था) एक फ़ाइल में 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(); 
    } 
} 

तुम भी pass a Context को यह करने के लिए, अगर और जब आप एंड्रॉयड के लिए इसे संशोधित, तो यह getResources() विधि का उपयोग कर सकते की आवश्यकता होगी।

आप शायद stop the android build tools from compressing the file पर भी जा रहे हैं, जो स्पष्ट रूप से केवल किया जा सकता है - यदि आप जीयूआई के साथ काम कर रहे हैं - फ़ाइल के विस्तार को जेपीजी जैसे कुछ बदलकर। इसने मेरे ऐप में लगभग 100 से 300 गुना तेज प्रक्रिया की।

NDK का उपयोग करके आप giving yourself more memory पर भी देख सकते हैं।

Answer 4

यहां कुछ ऐसा है जो मैंने जल्दी से एक साथ रखा है। यह दो फाइलों का उपयोग करता है, एक शब्द के साथ, दूसरे ऑफसेट के साथ।ऑफसेट फ़ाइल का प्रारूप यह है: पहले 10 बिट्स में शब्द का आकार होता है, अंतिम 22 बिट्स में ऑफ़सेट होता है (शब्द स्थिति, उदाहरण के लिए, aaah 0 होगा, अपमानजनक 4 होगा, आदि)। यह बड़े एंडियन (जावा मानक) में एन्कोड किया गया है। उम्मीद है कि यह किसी की मदद करता है।

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

मैं सी # में इन फ़ाइलों को बनाने, लेकिन यहां इसके लिए कोड (इसके साथ एक 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++; 
      } 
     } 
    } 
} 

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

हालांकि यह overkill की तरह ध्वनि सकता है, डेटा आप एक फ्लैट फ़ाइल के रूप में के साथ ऐसा करने की जरूरत है की दुकान नहीं है: और यह बाइनरी फ़ाइल खोज के लिए जावा कोड है। डेटाबेस बनाएं और डेटाबेस में डेटा पूछें। यह प्रभावी और तेज़ दोनों होना चाहिए।