Soundex

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 mars 2021; kontroller kräver 2 redigeringar .

Soundex  - en av algoritmerna för att jämföra strängar efter deras ljud; ställer in samma index för strängar som låter liknande på engelska .

Utvecklad av Robert C. Russel och Margaret King Odell och patenterad 1918 och 1922 [1] [2] , är historiskt sett den första fonetiska algoritmen . Blev populär på 1960-talet efter att flera artiklar ägnats åt det i Communications of the ACM och Journal of the ACM ; han blev ännu mer känd efter att ha medverkat i Knuths Konsten att programmera [3] . Det har använts som en standardfunktion i många RDBMS sedan 1980 -talet .

Inledningsvis fokuserad på fonetik för amerikansk engelska, genom modifieringar kan den appliceras på andra varianter och språk, men i vissa fall krävs betydande förändringar (som t.ex. i Deutsch-Mokotoff-algoritmen , som stöder egennamn i jiddisch och slaviska språk ). Därefter dök det också upp alternativ som fokuserade mer på vanliga engelska ord än på egennamn (som Metaphone , Caverphone ).

Algoritmsteg

  1. Kom ihåg första bokstaven i ordet.
  2. Alla förekomster av h och w tas bort (förutom den första bokstaven i ordet).
  3. Konsonanter ersätts med siffror från 1 till 6, och bokstäver med liknande klingande motsvarar samma siffror:
    • b, f, p, v → 1
    • c, g, j, k, q, s, x, z → 2
    • d, t → 3
    • l → 4
    • m, n → 5
    • r → 6
  4. Varje sekvens av identiska siffror reduceras till en sådan siffra.
  5. Alla a , e , i , o , u , y tas bort (förutom den första bokstaven i ordet).
  6. Ersätter det första tecknet med bokstaven som memorerades i steg 1, vilket gör det med stor bokstav.
  7. Den resulterande strängen trunkeras till de första fyra tecknen. Om strängen är mindre än den nödvändiga längden ersätts de saknade tecknen med en 0.

Exempel:

Anteckningar

  1. US-patent 1 261 167
  2. US-patent 1 435 663
  3. Donald Knuth . Del 6. Sökning // Art of Programming = The Art of Computer Programming. - 2012. - V. 3. Sortering och sökning. - S. 249.