我有一個很大的文本文件(5Mb),我在我的Android應用程序中使用。我將該文件創建爲預先分類的字符串列表,並且該文件一旦創建就不會更改。如何對這個文件的內容執行二分搜索,而不需要逐行讀取匹配的字符串?如何執行文本文件的二進制搜索
回答
由於文件內容沒有變化,所以可以將文件分成多個部分。說A-G,H-N,0-T和U-Z。這使您可以檢查第一個字符,並立即將可能的設置切割爲原始尺寸的四分之一。現在線性搜索不會花費太長時間,或者讀取整個文件可能是一個選項。如果n/4仍然過大,這個過程可能會延長,但這個想法是相同的。將搜索細分構建到文件結構中,而不是試圖在內存中完成所有操作。
我會第二個。此外,由於(根據你的描述),你會知道文件在其創建時的內容,可以進一步根據它包含字符串長度divite文件。所以A-G(1-5個字符),A-G(5個字符)等等。所以在搜索時,你會知道打開哪個文件。在閱讀文件的時候,你基本上會跳過N/4個元素。 – 2012-04-04 14:44:33
我嘗試此解決方案,有N/4之間很大的區別的log(n)這個非常醜陋的解決方案(對不起)還是要謝謝你。 – Beno 2012-04-04 17:09:12
@Beno:問題是,如果n/4 __can__適合內存,那麼你可以讀取較小的塊並進行二分搜索 - > 1 + log(n)= log(n)。它所做的只是處理二分搜索算法的第一次迭代,與以下迭代略有不同。 – unholysampler 2012-04-04 18:40:18
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
,如果該文件沒有固定寬度的行,那麼您不能輕鬆地執行二進制搜索,而無需首先將其加載到內存中,因爲您無法像使用固定寬度的行一樣快速跳轉到文件中的特定行。
我有65000行,每行是word。當我將該文件讀取到String []時,我會崩潰。每個單詞都有不同的長度。 – Beno 2012-04-04 18:30:53
在一個統一的字符長度的文本文件中,你可以尋找字符間距的中間字符,開始閱讀字符,直到你打開你的分隔符,然後使用後續字符串作爲元素明智中間的近似值。但是,在android中這樣做的問題顯然不能get random access to a resource(儘管我想你可以每次重新打開它)。此外,這種技術不會推廣到其他類型的地圖和集合。
另一種選擇是(使用RandomAccessFile)在文件的開始處編寫一個ints的「數組」 - 每個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();
}
}
您還需要pass a Context它,如果當你修改其Android系統,因此它可以訪問getResources()方法。
你也可能會想要stop the android build tools from compressing the file,這顯然只能做到 - 如果你正在使用GUI - 通過將文件的擴展名更改爲像jpg這樣的東西。這使得我的應用程序的處理速度提高了大約100到300倍。
您也可以使用NDK來查看giving yourself more memory。
這裏是我快速放在一起的東西。它使用兩個文件,一個包含文字,另一個包含偏移量。偏移文件的格式是這樣的:第一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));
}
}
雖然這聽起來有點小題大做,不存儲你需要作爲平面文件來做到這一點的數據。建立數據庫並查詢數據庫中的數據。這應該既有效又快速。
- 1. 執行二進制搜索
- 2. CircleCI:執行本地二進制文件
- 3. 如何檢索二進制文件的二進制版本號
- 4. 執行二進制搜索的問題
- 5. 二進制搜索文本框
- 6. 進入文件中間進行二進制搜索的方法
- 7. 如何做搜索/替換命令行「二進制」文件
- 8. CUDA二進制搜索執行
- 9. 在JavaScript中執行二進制搜索
- 10. 執行二進制搜索算法
- 11. lower_bound執行二進制搜索
- 12. 使用python執行二進制搜索
- 13. 搜索和二進制文件
- 14. 搜索在marklogic二進制文件
- 15. 在已排序字典文本文件上進行二進制搜索?
- 16. 如何從Atom Package執行本機二進制文件?
- 17. Erlang:在二進制文件中進行反向搜索
- 18. 忽略二進制文件的PowerShell搜索腳本
- 19. GCC編譯的二進制文件給予 「不能執行二進制文件」
- 20. g ++編譯的二進制文件給「不能執行二進制文件」
- 21. 無法執行二進制文件
- 22. 用shebang執行二進制文件
- 23. cygwin - 無法執行二進制文件
- 24. 在iPhone上執行二進制文件
- 25. C++不能執行二進制文件
- 26. bash,無法執行二進制文件
- 27. PhantomJs無法執行二進制文件
- 28. AWS:不能執行二進制文件
- 29. 無法執行二進制文件centos?
- 30. 從終端執行Java - 帶輸入文件的二進制搜索
逐行讀取並在每行上使用'包含()''類的'方法。 – 2012-04-04 11:28:26
使用Arrays.binarySearch()方法 – 2012-04-04 11:29:02
我不能閱讀所有的文件。我遇到了崩潰和內存異常。一行一行太慢 – Beno 2012-04-04 11:45:31