3. Textausschnitte schnell finden ?

Textausschnitte schnell finden ?

  • 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