strengen at søge algoritme

[Artem]

Hi guys

Jeg har fået til opgave, hvor enkelt streng der skal matches, og det er identifikator skal returneres.Gennemførelse via binære træ er ikke acceptabelt, da det tager hukommelse et parti.Hashing kan gøres, men problemet er, at sæt-strengen er undertermined og kan ændres i løbet af levende program udførelse, så jeg er nødt til at opretholde fleksible kollision liste for hashing algoritme.
Kunne nogen anbefale hash funktion med forudbestemt antal kollisioner for ubestemt antal input elementer (strings), hvor streng længde kan variere i intervallet 2-32 tegn.Der kan være op til 300 strenge, der skal matches og algoritme skal være hurtig nok til at håndtere matching i realtid.String længde kan variere mellem 2 - 32 tegn.
Særlige litteratur for hashing vil også blive værdsat.

Nuværende gennemførelse bruger hybrid n-store træ med tilknytning element listen for hvert træ node hvor sekventiel søgning er gjort for at finde match for nuværende n-th holdning karakter.Denne algorith har deterministiske tid til udførelse buit det er ret lang og ineffektiv.

På forhånd tak

 

[luben111]

Hej,

Jeg lavede for nogen tid siden et projekt, hvor jeg var nødt til at opdage 60 forskellige tråde med forskellig længde og hurtigt til at svare.Faktisk er det tid til respons var så begrænset, at jeg virkelig var i knibe.

Løsningen blev mere end simpel - CRC16 - Jeg gør CRC 16 i de kommende strengen af data.Når jeg får CR / LF jeg sammenligne CRC med etalons i rom ...anlæg stor.

Hvis du har brug for mere pålidelige arbejder (faktisk CRC16 er mere end enought) kan du bruge CRC32.

Brug tabellen tilgang gør beregning af CRC for enkelt byte 10-12 instruktioner!

Hope this helps
Luben

 

[Artem]

Hi Luben

Tak for svaret.Det er interessant, men littled bit forskellige fra, hvad jeg beskæftiger mig.Kan jeg ikke forklare dette korrekt, input strengen kan være en som ikke er i hash-tabel, så hashing funktion bør erkende, at det ikke er i tabellen,
selvom nøglen produceret af hash funktion matcher strengen allerede indsat i hash bord.

For fast antal input strengen der er enkel algoritme leveret af GNU, genererer C kildekoden er nødvendige for foruddefineret sæt strenge - gpref anvendelighed, men det er ikke egnet til min sag.

 

[luben111]

Måske er jeg ikke forklare i detaljer:

Du sammenligner ikke strygere - CHAR ved CHAR, men du sammenligne hele strings (færdig med CR / LF).Du sammenligner faktisk er to 16 bit cifre - meget enkel og hurtig sammenligning.

Der er ingen forskel, hvordan du sammenligner - CHAR ved CHAR, eller du får CRC16 af de kommende string og du sammenligne den med den etalons i ROM (for hver streng 2 bytes .., der
er meget mindre end at holde hele strings).

Du behøver ikke at vide præcis input string - du lige vil vide, at det passer strengene (deres CRC) i tabellen eller ej.Du kan tilføje nye strings også ...

Jeg er enig i, at den fremgangsmåde, lyder vanvittigt, men virkelig fungerer pålideligt i mit projekt for GSM modul kontrol.Hilsen
Luben

 

[Artem]

Hi Luben

Jeg ved, at jeg vil først producere CRC16 af input strengen, der skal matches, så jeg kan indeksere det via tabel (men da det er 2 bytes tabellen skal
65.535 poster) eller sammenligne en efter en alle CRC koder precalculated for strygere, der skal matches og lagres som konstanter i rom.

Jeg ment, at CRC-kode beregnet for en streng (lad sige " CMTI" uopfordret reaktion i din appl) er ikke enestående, og der kunne være andre strengen, der giver nøjagtig samme CRC kode.Hvis denne streng
(som har samme CRC har koden som den
registreret i hash tabellen " CMTI" string)
er ikke i hash-tabel, output fra CRC funktion vil pege på den CMTI streng.
Når input sæt strenge apriori er ikke deterministisk, er der sandsynlighed for, at CRC kode fik fra hash-funktionen kunne
punkt til registrerede en - kollision sag.
Et andet spørgsmål, gør CRC16 algoritmen perfekt distribuere alle GSM Modem AT svar strengene i unik nøgle og hvis der er sammenstød, hvor mange kollisioner du har for alle GSM Modem svar strings?

 

[luben111]

Hej,

Synes, at du misundersand mig ....

>>> Jeg ved, at jeg vil først producere CRC16 af input strengen, der skal matches, så jeg kan indeksere det via tabel (men da det er 2 bytes tabellen skal
65.535 poster) eller sammenligne en efter en alle CRC koder precalculated for strygere til blive matchet og lagres som konstanter i rom.

Nej ..Jeg har ikke betyde, at.Jeg har CRC16 regnemaskine, så jeg kan nemt beregne (i hånden eller med programmet) af alle ønskede strings CRC (CRC16 regnemaskinen er andet udstationeret i electroda gerne fil).Så hvis jeg er nødt til at søge inden for 300 strengene, jeg har brug for 300 16 bit ord = 600 bytes!Ingen af de kendte algorythms kan producere sådanne kompakt og hurtigt sammenligne ..ingen!>>> Jeg ment, at CRC-kode beregnet for en streng (lad sige " CMTI" uopfordret reaktion i din appl) er ikke enestående, og der kunne være andre strengen, der giver nøjagtig samme CRC kode.Hvis denne streng
(som har samme CRC har koden som den
registreret i hash tabellen " CMTI" string)
er ikke i hash-tabel, output fra CRC funktion vil pege på den CMTI streng.

Jeg ved, hvad du mente ...men muligheden 2 strings at have samme CRC16 er præcis 1 / 65000.Hvis du bruger CRC32 praktisk du aldrig har problemer.>>> Et andet spørgsmål, gør CRC16 algoritmen perfekt distribuere alle GSM Modem AT svar strengene i unik nøgle og hvis der er sammenstød, hvor mange kollisioner du har for alle GSM Modem svar strings?

Ingen ...Jeg har aldrig haft problemer.Jeg brugte AT89C2041 at spore over 60 svar med meget forskellig længde.Desuden var dette den
12. MHz (1 MIPS) - ingen algorythm var i stand til at gøre dette i sådanne kompakte volumen.Jeg prøvede alt forgæves - forarbejdningsvirksomheden var for langsomt (og vi havde ikke at ændre det).

Som jeg fortalte dig, det
er meget skøre tilgang - men bare prøve det.For mig virker det meget - jeg har aldrig haft problemer ...Jeg kan ikke sammenligne strengene, jeg ved ikke samle strengen i hukommelsen (ingen buffer kræves),
ved jeg ikke holde etalons i hukommelsen ....hvad du ønsker mere? ...måske en øl

<img src="http://www.edaboard.com/images/smiles/icon_smile.gif" alt="Smile" border="0" />Hilsen
Luben

 

[luben111]

Jeg glemte noget ...

Denne tilgang kræver særlig afgrænsningstegn strengen, nogle tegn, der vil fortælle dig, hvor er i slutningen af strengen.I GSM-moduler dette er ingen probllem - CR / LF

Indtil du får afgrænsningstegn du bare sætte de kommende data til CRC16 register - ingen sammenligninger - meget hurtigt!

Når du får afgrænsningstegn, først da du sammenligne CRC16 værdi i registeret med etalons i rom.Hvis du har brug for 300 kommandoer, du har brug for 600 bytes.Du sammenligner 2 16 bit cifre.Faktisk strengene kan være meget lang, men for hver streng, du behøver kun 2 bytes.Hvis du
er bange - brug CRC32 - Jeg sværger, at du aldrig
vil få lige CRC32 for to strygere .....prøv med hånden for at gøre dette.

Som jeg fortalte dig mulighed 2 strings at have samme CRC er meget, meget, meget lille.Bare glem det!Jeg har aldrig haft så heldig at se 2 strygere med samme CRC ...Hvis dette sker, kan du nemt tilføje en ekstra karakter i register (for at starte ikke fra nul i begyndelsen), og problemet vil forsvinde.Tro mig, det
er fantastisk, og efter at jeg har opdaget det, jeg aldrig bruge andre en.

 

[Artem]

Jeg har prøvet en anden tilgang, bare for at teste og ikke brugte har bordet.Kildekoden er i vedhæftet fil.Opslagsfeltet fortælling er bygget af en anden fucntions som tager strygere og identifikatorer som argument.Denne fil indeholder kun string matching og opslagstabelnavn contant.Du kan kompilere og teste programmet, kan perfomr nogle benchmarking mod dine algoritme.
Beklager, men du skal login for at se denne tilslutningskrav

 

[luben111]

I fald et kig på din tabeller ....

Faktisk til at beregne CRC16 hurtigt (tabellen tilgang) du har brug for 512 bytes af rom til hurtig beregning af CRC16.Så for begrænset antal strygere min tilgang kunne give større kode.

For den hastighed der er ingen sammenligning.Jeg kan ikke sammenligne strygere, indtil jeg får det afgrænsningstegn (Det sparer en masse tid).

Når afgrænsningstegn fandt jeg sammenligne to 16 bit cifre i tabellen med en klar struktur - ordet array.Strengene med forskellige længde skabe eller "grim" array eller array med for mange nuller.Du kan beregne alene at sammenligne en 16 bit ord med array af 16 bit ord sis meget hurtig procedure ...og det
er gjort en gang pr incomming streng.Indtil der er ingen afgrænsningstegn, strengen sammenligning næsten ikke forbruge op ressourcer.

Som jeg husker strengen tilgang i mit system var bare umuligt at køre med hastigheder på over 1200 (om 89C4051 / 20MHz).Efter overgangen til CRC16 jeg var i stand til at nå hastigheder på 56000K!Jeg taler om pålidelig drift - når jeg oversvømme modul med tilfældige non-stop data stream - hvis modul overlevet - det
er OK, hvis blot én ubesvarede byte syntes - hastigheden er højere end det kan tage.

Men hvis du ikke
er sikker på om min tilgang,
er du velkommen til at bruge det klassiske en.Jeg kan fortælle kun, at min tilgang i store arrays kan være flere gange hurtigere derefter strengen tilgang.Og jeg er enig i, at nogle meget lille mulighed foreligger 2 strings at give samme CRC16 (1 / 65000).

Hvis du ikke drage omsorg for den hastighed, du kan beregne CRC med program - så har du jo næsten lig med streng tilgang hastighed (men stadig hurtigere) og fantastiske komprimering af rom-hukommelse.

Hvis du ønsker yderligere oplysninger - e-mail mig og jeg kan sende dig kilder til mit projekt.It's GSM telefonsvarer - når nogen kalder modul det hænger og starter samtalen.Brugeren kan annullere opkaldet AOR bryde samtalen.Måske ~ 70 sådanne moduler arbejder permanent (næsten 24 timer om dagen) lige nu og jeg har aldrig haft nogen problemer med dem ....Dette var min sidste projekt uden RTOS efter dette projekt jeg skiftet fuldstændig til RTOS.Den algorythm beskrives med ord lyder meget simpelt, men når du gør det på blokke vil du opleve, at lineær programmering kan støtte mange dele af algorythm ...For sikker på, at du
får brug RTOS såvel.

Venlig hilsen
Luben Hristov
luel (at) mbox.cit.bg

 

[Artem]

Hej

Nej, jeg mener ikke, at Deres fremgangsmåde er god eller dårlig - det er lige til at dele idé.
Opslagstabellen i mit program er ikke kun par strygere, det er sorteret forbundet liste / træ baseret data struktur.Jeg har netop ændret programmet for at køre det enkeltstående og foretaget nogle tests for de fleste af de anvendes på solic og unsolic svar.
Hvad jeg har fundet er, at max antal gentagelser i strtoid () funktion er omkring 30.En iteration omfatter kun én byte sammenligning og pointer justering (som er summen drift) i opslagstabellen.
Antallet af gentagelser (sammenligninger) er afhængig af indhold
ligestilling mellem søgeord, på grund af sortering princippet bruges, når bygningen opslagstabel.For worst case, hvor lad sige 50 bogstaver, som anvendes til at kode 16 tegn lang streng, antal gentagelser vil være 50 * 16 =
800 byte sammenligning, men det er langt væk fra virkelige sager.

Det er også interessant at se din gennemførelse.Kunne du sende det?Også, den funktion er naturligvis paaberaabes efter afgrænsningstegn vil blive fundet, så
input til strtoid er null henlagt Tegnstreng.

Se kildefilen det kunne være interessant. Jeg har brugt bc45 eller bcc55.
Beklager, men du skal login for at se denne tilslutningskrav

 

[Artem]

Beklager problem med filen
Beklager, men du skal login for at se denne tilslutningskrav

 

[luben111]

Her er kildekoden på den fil ....CRC16, GSM kommando dekodning og smart svar.

Faktisk er dette ikke ligefrem er den sidste version - her kan du se afkodning af 30-40 kommandoer og hastigheden er stadig 9600, men det
er afprøvet i virkelige formål og endda i øjeblikket arbejder i nogle enheder.Håber, at dette vil hjælpe dig ...

Venlig hilsen
Luben
Beklager, men du skal login for at se denne tilslutningskrav