*ausgrab* ^^
Hab mich eben wieder mit dem Thema beschäftigt, weil ich schon ewig eine Idee im Kopf hatte. Und zwar verwende ich für meine Suche zeichenweises, rekursives Hashing.
Für die Implementierung verwende ich C++ ohne irgendwelche Zusatzbibliotheken. Kompiliert wird das ganze also einfach mit:
Hier eine Proof-of-Concept-Implementierung, die bestimmt noch optimierungsfähig ist:
Code: Alles auswählen
// main.cpp
#include <iostream>
#include <vector>
#include "HashData.h"
int main( int argc, char *argv[] )
{
if( argc < 3 )
{
std::cout << "./find [file] [text]" << std::endl;
return 1;
}
HashData data( argv[1] );
std::vector<int> results = data.find( argv[2] );
for( unsigned int i = 0; i < results.size(); i++ )
std::cout << ( results[i] + 1 ) << ": " << data.line( results[i] ) << std::endl;
return 0;
}
Code: Alles auswählen
// HashData.h
#ifndef HASHDATA_H
#define HASHDATA_H
#include <map>
#include <string>
#include "LetterEntry.h"
class HashData
{
public:
HashData( const char *const path );
std::vector<int> find( const char *const searchItem );
std::string line( const int index );
protected:
void organizeData();
private:
void loadFile( const char *const path );
std::vector<std::string> m_lines;
std::map<char, LetterEntry> m_data;
};
#endif
Code: Alles auswählen
// HashData.cpp
#include "HashData.h"
#include <fstream>
HashData::HashData( const char *const path )
{
loadFile( path );
organizeData();
}
std::vector<int> HashData::find( const char *const searchItem )
{
return m_data[searchItem[0]].find( searchItem );
}
void HashData::organizeData()
{
std::vector<std::string>::iterator it;
int i = 0;
for( it = m_lines.begin(); it != m_lines.end(); it++, i++ )
{
for( unsigned int j = 0; j < it->length(); j++ )
{
if( j == 0 || it->at( j - 1 ) == ' ' )
m_data[it->at( j )].add( it->c_str(), i );
}
}
}
std::string HashData::line( const int index )
{
return m_lines[index];
}
void HashData::loadFile( const char *const path )
{
std::ifstream is( path );
int c;
m_lines.push_back( std::string() );
while( is.good() )
{
c = is.get();
if( c == '\n' )
m_lines.push_back( std::string() );
else
m_lines.back().push_back( c );
}
is.close();
}
Code: Alles auswählen
// LetterEntry.h
#ifndef LETTERENTRY_H
#define LETTERENTRY_H
#include <map>
#include <vector>
class LetterEntry
{
public:
void add( const char *const text, const int lineIndex );
std::vector<int> find( const char *const searchItem );
private:
std::map<char, LetterEntry> m_data;
std::vector<int> m_lineIndexes;
};
#endif
Code: Alles auswählen
// LetterEntry.cpp
#include "LetterEntry.h"
void LetterEntry::add( const char *const text, const int lineIndex )
{
m_lineIndexes.push_back( lineIndex );
if( *( text + 1 ) != '\0' )
m_data[text[1]].add( text + 1, lineIndex );
}
std::vector<int> LetterEntry::find( const char *const searchItem )
{
std::vector<int> results( m_lineIndexes );
if( m_data.count( searchItem[1] ) > 0 )
{
std::vector<int> prev = m_data[searchItem[1]].find( searchItem + 1 );
results.insert( results.end(), prev.begin(), prev.end() );
}
return results;
}
Beispielaufruf mit der obigen Datei "main.cpp", wobei nach "argv" gesucht wird:
Code: Alles auswählen
$ ./find main.cpp argv
6: int main( int argc, char *argv[] )
8: if( argc < 3 )
14: HashData data( argv[1] );
15: std::vector<int> results = data.find( argv[2] );
Das ganze geht natürlich auch mit Leerzeichen:
Code: Alles auswählen
$ ./find main.cpp "unsigned int"
16: for( unsigned int i = 0; i < results.size(); i++ )
Als Ergebnis wird die Zeilennummer und der Text der Zeile ausgegeben, das Prinzip wäre aber leicht auch noch auf Zeichen innerhalb der Zeile verbesserbar. Das Löschen von Daten fehlt ebenfalls noch, sollte aber auch in linearem Aufwand möglich sein.
Vorteil: Linearer Suchaufwand (bezüglich des gesuchten Textes), unabhängig von der Länge des gesamten Textes
Nachteil: Hoher Speicherbedarf (ein vielfaches der Eingabe, abhängig von der Anzahl der Einheiten, in dieser Implementierung also Wörter); nicht-zusammenhängende Matches (z.B. "unsigned i" in "unsigned int i" zu finden) dürfte schwerer werden
Bei vielen Ergebnissen wird das zurückgeben der Vektoren in LetterEntry::find() aufwendig... kann ich das noch optimieren? Eigentlich bräuchte ich da ja nur eine flache Kopie, da ich die sowieso in einem neuen Vektor zusammenhänge. Kann ich das außer mit Zeiger auf private Objekte noch anders (eleganter) lösen?
Hab ich damit eigentlich das Rad neu erfunden? ^^ Gibts diesen Algorithmus schon unter einem bestimmten Namen? ^^
Für Fragen bzw. Optimierungs- und Implementierungs-Vorschläge bin ich natürlich offen
