3. Textausschnitte schnell finden ?

Textausschnitte schnell finden ?

  • G

    Ich hab momentan ein Array, der voll mit Textstrings ist.
    Die Textstrings sind aufgebaut wie beispielsweise "Die Ärzte - Ein Song namens Schunder" (also ähnlich von mp3-dateinamen)

    Im Array sind etwa 10.000 solcher Strings drin.
    Nun möchte ich in meinem Programm alle Strings nach einem bestimmten Teil-String durchsuchen. Ich suche z.B. nach allen Strings, in denen "song" vorkommt.
    Momentan wandere ich da durch jeden einzelnen String mit ner Schleife durch. Das geht eigentlich recht fix, aber ich frage mich ob es da nicht ne effizientere Möglichkeit gibt - so'ne Art Mini-Datenbank oder sowas...

    0
  • P

    Wenn du beliebigen Substrings suchst (also nicht nur nach Titelanfang, und nicht nur nach bestimmten Zeichenketten), wird auch eine Datenbank dir nicht weiterhelfen. Die muß in dem Fall auch alle Strings durchsuchen.

    Es gibt sicher ein paar Sachen, wo man optimieren kann, aber die sind recht aufwendig.

    Was sich machen läßt:

    a) Substring-Suche optimieren
    Es gibt ein paar ganz abgehobene Optimierungen für die Suche von Teilstrings. Für "kleine Teilstrings in kleinen Suchtexten" wird da aber weniger am Algorithmus, als Datenspeicherung usw. zu drehen sein.

    Die übliche strstr - Implementation nutzt eine vorher bekannte Stringlänge nicht aus (VC nutzt diese auch für CString::Find). Hier läßt sich noch was rausholen... Außerdem kann man mit einer Voranalyse des Suchbegriffs noch einiges gewinnen - auch das ist in der standardimpl nicht drin, weil sich das nur bei mehrfachen Vergleichen wirklich lohnt

    b) Case Sensitive Search
    das heißt normalerweise, daß man mit einer Kopie der Stringtabelle arbeiten muß, die alles in Kleinbuchstaben ist, und den Suchbegriff vor der Suche in Kleinbuchstaben umwandelt

    c) Hash-Tabelle für häufige Suchbegriffe
    Hilft aber nix für beliebige Begriffe

    d) Evtl. gibt es Substring-fähige "Fingerprint"-Algorithmen, kann mir aber beim besten willen nix dergleichen vorstellen...

    0
  • R

    mir würde folgende Methode einfallen, wenn du immer nur nach Woertern suchst

    du erzeugst fuer jedes Wort eine Art Code, zB. bestehend aus

    <laenge><allebuchstabenaddiert>

    also zum Beispiel bei dem Wort "substring" sähe die Zahl dann so aus (wobei a die 1 hat usw.) 9129

    nun speicherst du fuer jeden Text eben die Zahlen fuer jedes Wort ab und bei einem Vergleich, musst du dann nur gucken, ob irgend eine Zahl gleich der Zahl fuer das gesuchte Wort ist.

    Das Problem ist eben nur, dass du mehr Speicher brauchst und ein Insert in die Datenbank viel teurer ist (da du ja die ganzen Zahlen errechnen musst)

    0
  • P

    @kingruedi: das klappt nur bei ganze-Wort-Treffer...
    (ist im Prinzip die Hash-Tabelle mit "alle ganzen Worte" als häufige Suchbegriffe)

    0
  • G

    peterchen schrieb:

    @kingruedi: das klappt nur bei ganze-Wort-Treffer...

    wieso?

    also

    "ein bsp satz"
"ein zweiter satz"
"einer muss noch"

    als ersten schrit machen wir mal eine code tabelle, jedes wort kriegt eine id

    ein = 1
bsp = 2
satz = 3
zweiter = 4
einer = 5
muss = 6
noch = 7
//die tabelle sollte nach alphabet sortert sein damit binäre suche möglich ist

    jetzt legt man ein zwei dimensionales array an,

    std::vector<std::vector<int> > v( 3 );
//jetzt fügen wir den ersten satz ein
v[0].push_back( 1 ); v[0].push_back( 2 ); v[0].push_back( 3 );
//und jetzt nr. 2
v[1].push_back( 1 ); v[1].push_back( 4 ); v[1].push_back( 3 );
//und jetzt nr. 3
v[2].push_back( 5 ); v[2].push_back( 6 ); v[2].push_back( 7 );

    wenn wir jetzt nach den wort satz suchen wollen, dann kucken wir in die erste tabelle nach der id für "satz"
    dann durchsuchen wir das zweite array nach der id 3

    wenn man aber nur nach der zeichen folge "ei" suchen will durchsucht man die erste tabelle nach wortern die "ei" enthalten
    das wären im bsp. ein zweiter einer und jetzt sucht man im zweiten array anhand der ids

    die aufgabe lässt sich schön in kleine häpchen aufteilen, daduch wird sie leichter implementierbar und am ende kann man das hinter einer schönnen schnittstelle kapseln

    aber irgend wie habe ich das gefühl das eine db genau diese aufgaben für einen macht

    0
  • G

    Danke schonmal...
    Nur so nebenbei: Mir ist aufgefallen das windows den speicher in dem die daten liegen gerne auslagert, wenn nen paar Minuten lang nicht drauf zugegriffen wird. Wenn dann eine Suche gestartet wird, braucht er relativ lange für die nächsten 1-3 Suchanfragen, die anschließend in wenigen Milisekunden fertig sind. Gibts ne Möglichkeit das im RAM zu lassen ? (z.B. einfach alle paar meter einfach einmal kurz drauf zu greifen ?)

    0
  • P

    @Dimah:
    gut, bringt was für häufige Worte, die Frage ist - wieviel (Man hat das gleiche Problem - freie Substring-Suche, wenn auch für vielleicht Faktor 10 weniger Werte und kürzere Strings, aber dafür dann noch einen zweiten Lookup, der - bei dem gegebenen Implementationsvorschlag - nochmal min O(N) x O(Wortzahl) geht. Das kann man zwar mit einem geeigneten Hash und einem sortiertem lookup runterbrechen, aber meiner Erfahrung nach hat der Lookup für die Substring-Suche reichlich konstanten Overhead, so daß man da nicht mehr wirklich viel gewinnt.

    Und eine "Mini-DB" macht dir das auf keinen Fall: da kriegst du nen sortierten Index, sonst nix. LIKE 'xyz*' - Abfragen kriegst du damit hin, aber nicht 'LIKE *xyz*'. Einen automatischer Hash mit Substring würde ich bestenfalls von SQL Server/Oracle aufwärts erwarten.

    @geeky: eigentlich nur, wenn der Speicher für was anderes gebraucht wird.

    Gibts ne Möglichkeit das im RAM zu lassen ?

    Nicht wirklich 😉
    10.000 x ca. 40 == 400K, die sind normalerweise so schnell wieder eingelagert... Es sei denn, deine Strings sind wild verteilt. Was nimmst du denn als String-Klasse, und was läuft denn noch so ab?

    0
  • R

    du kannst je nach System einige Pages im RAM locken. Wie das unter Windoze geht, weiss ich nicht.

    0
  • P

    @kingruedi: Nur im Kernel Mode, also in einem Driver 😉

    Swapping ist bei der Datenmenge normalerweise auch kein problem, es sei den
    - der heap ist wahnsinnig fragmentiert
    - Der physische Speicher reicht vorn und hinten nicht

    0
  • G
     

    typedef struct daten
{
    char suchzeile[150];
    char addinfo1[50];
    char addinfo2[50];
    char addinfo3[50];
    int addinfo4;
} daten;

daten *datenRay;

datenRay=(daten*)malloc( 2000 * sizeof(daten) );

...

    ...ungefähr so sieht das in meinem app aus...
    Ich geh dann mit ner Schleife durch mein "datenRay" und mache meinen Textvergleich nur in dem Element "suchzeile"

    0
  • ?

    hallo

    guck mal auf http://www.droopyeyes.com/default.asp?mode=ShowProduct&ID=4 das ist wirklich eine sehr schnelle stringroutine. und vorallem freeware.

    Meep Meep

    <edit by kingruedi>url-tag gefixed</edit>

    0
  • G

    thx!

    0
  • W

    kingruedi schrieb:

    mir würde folgende Methode einfallen, wenn du immer nur nach Woertern suchst

    du erzeugst fuer jedes Wort eine Art Code, zB. bestehend aus

    <laenge><allebuchstabenaddiert>

    also zum Beispiel bei dem Wort "substring" sähe die Zahl dann so aus (wobei a die 1 hat usw.) 9129

    Du hast dabei bereits auf ein Problem hingedeutet. Ein weiteres wäre, dass, wenn c die Kodierungsfunktion wäre

    c("Substring") == c("gnirtsbuS") == 9129

    wäre. Mit anderen Worten. Für c gibt es keine Umkehrfunktion, was elementar wichtig für Kodierungsfunktionen ist.

    0
  • R

    @WebFritzi
    Also ich ging davon aus, dass der ursprungs-String erhalten bleibt und man bei einer Übereinstimmung der Checksumme eben nochmal das Wort im ursprungs-String prüft.

    Wobei es beim praktischen Gebrauch eh wenig Überschneidungen geben sollte

    0
Anmelden zum Antworten