Inputförbättring (datavetenskap)
Inom datavetenskap är indataförbättring principen att bearbetning av en given indata till ett problem och ändring av den på ett specifikt sätt kommer att öka körtidseffektiviteten eller utrymmeseffektiviteten , eller båda. Den ändrade ingången lagras vanligtvis och nås för att förenkla problemet. Genom att utnyttja strukturen och egenskaperna hos ingångarna skapar ingångsförbättringar olika snabbare algoritmers effektivitet .
Sökande
Inputförbättring vid sökning har varit en viktig komponent i algoritmvärlden under en tid inom datavetenskap. Huvudtanken bakom denna princip är att effektiviteten av en sökning är mycket snabbare när det tar tid att skapa eller sortera en datastruktur för den givna ingången innan man försöker söka efter elementet i nämnda datastruktur.
Presortering
Presortering är tekniken att sortera en indata innan du försöker söka den. Eftersom tillägget av en sorteringskomponent till en algoritm läggs till sökalgoritmens körtid och inte multipliceras, tävlar den bara om den långsammaste delen av algoritmen. Eftersom effektiviteten hos algoritmer mäts av den långsammaste komponenten är tillägget av sorteringskomponenten försumbar om sökningen är mindre effektiv. Tyvärr är försortering vanligtvis den långsammaste komponenten i algoritmen. Som kontrast är en sökalgoritm utan en försortering nästan alltid långsammare än den med en försortering.
Sorteringsdelen av algoritmen bearbetar inmatningen av problemet innan den sökande delen av algoritmen ens nås. Att ha elementen i inmatningen sorterade i någon sorts ordning gör sökningen trivial i praktiken. De enklaste sorteringsalgoritmerna – infogningssortering , urvalssortering och bubbelsortering – har alla en värsta körtid på O( n 2 ), medan de mer avancerade sorteringsalgoritmerna – heapsort , merge sort – som har en körtid i värsta fall på O( n ) . log n ) – och quicksort – som har ett värsta fall av O( n 2 ) men är nästan alltid O( n log n ). Genom att använda dessa sorteringsalgoritmer kommer en sökalgoritm som innehåller försortering att ge dessa stora effektivitetsvinster.
Ett enkelt exempel på fördelarna med försortering kan ses med en algoritm som kontrollerar en array för unika element: Om en array med n element ges, returnera true om varje element i arrayen är unikt, annars returneras false. Pseudokoden presenteras nedan :
algoritmen uniqueElementSearch(A[0... n ]) är för i := 0 till n – 1 gör för j := i + 1 till n gör om A[ i ] = A[ j ] returnerar sedan falsk return true
Utan en försortering, i värsta fall, skulle denna algoritm kräva att varje element kontrolleras mot alla andra element med två möjliga utfall: antingen finns det inget dubblettelement i arrayen, eller så är de två sista elementen i arrayen dubbletter. Detta resulterar i en O( n2 ) -effektivitet.
Jämför nu detta med en liknande algoritm som använder försortering. Denna algoritm sorterar den inmatade matrisen och kontrollerar sedan varje par av element för en dubblett. Pseudokoden presenteras nedan:
algorithm presortUniqueElementSearch(A[0... n ]) är sort(A[0... n ]) för i := 0 till n – 1 gör om A[ i ] = A[ i + 1] returnerar sedan falsk retur Sann
Som tidigare nämnts är den minst effektiva delen av denna algoritm sorteringen av arrayen, som, om en effektiv sortering väljs, skulle köras i O( n log n ). Men efter att arrayen har sorterats behöver arrayen bara korsas en gång, vilket skulle köras i O( n ). Detta resulterar i en O( n log n ) effektivitet.
Det här enkla exemplet visar vad som är kapabelt med en indataförbättringsteknik som försortering. Algoritmen gick från kvadratisk körtid till linjärtmisk körtid vilket kommer att resultera i snabbare för stora ingångar.
I träd
Att skapa datastrukturer för att mer effektivt söka igenom data är också en form av inputförbättring. Att placera data i ett träd för att lagra och söka igenom indata är en annan populär teknik. Träd används inom datavetenskap och många olika typer av träd - binära sökträd , AVL-träd , rödsvarta träd och 2-3 träd för att bara nämna några få - har utvecklats för att korrekt lagra, komma åt och manipulera data samtidigt som upprätthålla sin struktur. Träd är en huvudsaklig datastruktur för ordboksimplementering.
Fördelarna med att placera data i ett träd är stora, speciellt om data manipuleras eller genomsöks upprepade gånger. Binära sökträd är den enklaste men ändå vanligaste typen av träd för denna implementering. Infogning, radering och sökning av objekt i ett träd är alla värsta fall O( n ), men exekveras oftast i O(log n ). Detta gör den upprepade sökningen av element ännu snabbare för stora ingångar. Det finns många olika typer av binära sökträd som fungerar mer effektivt och till och med självbalanserar vid tillägg och borttagning av objekt, som AVL-trädet som har ett värsta fall O(log n ) för all sökning, infogning och borttagning.
Att ta sig tid att lägga in den inmatade datan i en sådan struktur kommer att ha stora hastigheter för upprepad sökning av element, i motsats till att söka igenom data som inte har förbättrats.
Strängmatchning
Strängmatchning är en komplex fråga i programmeringsvärlden nu när sökmotorer är i framkanten av internet och onlinevärlden . När man får ett nyckelord eller en sträng som behöver sökas bland miljontals och åter miljoner ord, skulle det ta otroligt lång tid att matcha detta strängtecken per tecken. Ingångsförbättring gör att en ingång kan ändras för att göra denna process så mycket snabbare.
Brute -force- algoritmen för detta problem skulle fungera enligt följande: När den presenteras med en sträng med n tecken, ofta kallad nyckeln eller mönstret, skulle strängen jämföras med varje enskilt tecken i en längre sträng m , ofta kallad texten. Om ett matchat tecken förekommer, kontrollerar det det andra tecknet i nyckeln för att se om det matchar. Om den gör det, kontrolleras nästa tecken och så vidare tills strängen matchar eller det efterföljande tecknet inte matchar och hela tangenten flyttar ett enda tecken. Detta fortsätter tills nyckeln hittas eller tills texten är slut.
Denna algoritm är extremt ineffektiv. Det maximala antalet kontrollförsök skulle vara m - n +1 försök, vilket gör big-O-effektiviteten i värsta fall O( mn ). I genomsnitt skulle det maximala antalet kontrollförsök aldrig nås och endast ett fåtal skulle utföras, vilket resulterade i en genomsnittlig tidseffektivitet på O( m + n ) .
På grund av nödvändigheten av mer effektiva strängmatchningsalgoritmer har flera snabbare algoritmer utvecklats, där de flesta av dem använder idén om ingångsförbättring. Nyckeln är förbehandlad för att samla information om vad man ska leta efter i texten och den informationen lagras för att kunna hänvisa tillbaka till dem vid behov. Åtkomsten av denna information är konstant tid och ökar avsevärt körtidseffektiviteten för algoritmerna som använder den, mest kända Knuth-Morris-Pratt- algoritmen och Boyer-Moore- algoritmen. Dessa algoritmer använder för det mesta samma metoder för att få sin effektivitet med den största skillnaden i hur nyckeln är sammansatt.
Horspools algoritm
Som en demonstration av ingångsförbättring i strängmatchning bör man undersöka en förenklad version av Boyer-Moore-algoritmen, Horspools algoritm. Algoritmen börjar vid det n :te tecknet i texten m och jämför tecknet. Låt oss kalla detta tecken x . Det finns 4 möjliga fall av vad som kan hända härnäst.
Fall 1 : Det första möjliga fallet är att tecknet x inte finns i nyckeln. Om detta inträffar kan hela nyckeln förskjutas längden på nyckeln.
Fall 2 : Det andra möjliga fallet är att tecknet x inte är det aktuella tecknet, utan x är i nyckeln. Om detta inträffar, flyttas tangenten för att justera förekomsten längst till höger av tecknet x .
Fall 3 : Det tredje möjliga fallet är att tecknet x matchar det sista tecknet i nyckeln men de andra tecknen matchar inte helt och x förekommer inte igen i nyckeln. Om detta inträffar kan hela nyckeln förskjutas längden på nyckeln.
Fall 4 : Det fjärde och sista möjliga fallet är att tecknet x matchar nyckeln men de andra tecknen inte helt matchar nyckeln och x förekommer igen i nyckeln. Om detta inträffar flyttas tangenten för att justera förekomsten längst till höger om tecknet x .
Detta kan tyckas som om det inte är mer effektivt än brute-force-algoritmen eftersom det måste kontrollera alla tecken vid varje kontroll. Så är dock inte fallet. Horspools algoritm använder en skifttabell för att lagra antalet tecken som algoritmen ska skifta om den körs in i ett specifikt tecken. Inmatningen är förberäknad till en tabell med alla möjliga tecken som kan påträffas i texten. Skiftstorleken beräknas med två alternativ: ett, om tecknet inte finns i tangenten, är skiftstorleken n , nyckelns längd; eller två, om tecknet förekommer i tangenten, är dess skiftvärde avståndet från den högra förekomsten av tecknet i de första n -1 tecknen i tangenten. Algoritmen för skifttabellsgeneratorn ges nyckeln och ett alfabet av möjliga tecken som kan förekomma i strängen (K[0... n -1]) som indata och returnerar skifttabellen (T[0... s -1]). Pseudokod för skifttabellsgeneratorn och ett exempel på skifttabellen för strängen 'POTATO' visas nedan:
algorithm shiftTableGenerator(K[0... n -1]) är för i = 0 till s – 1 till T[ i ] := m för j := 0 till n – 2 till T[P[ j ]] := n – 1 – j returnera T
| tecken x | A | B | C | ... | O | P | ... | T | ... | Z | _ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| skifta värde | 2 | 6 | 6 | 6 | 4 | 5 | 6 | 1 | 6 | 6 | 6 |
Efter att skifttabellen har konstruerats i ingångsförbättringssteget, radar algoritmen upp nyckeln och börjar exekvera. Algoritmen körs tills en matchande delsträng av text m hittas eller nyckeln överlappar de sista tecknen i text m . Om algoritmen stöter på ett teckenpar som inte matchar, kommer den åt tabellen för tecknets skiftvärde och skiftar därefter. Horspools algoritm tar nyckeln (K[0... n -1]) och texten (M[0... m -1]) och matar ut antingen indexet för den matchande delsträngen eller strängen "Key not found" beroende på på resultatet. Pseudokod för Horspools algoritm presenteras nedan:
algorithm HorspoolsAlgorithm(K[0... n -1]), M[0... m -1]) är shiftTableGenerator(K[0... n -1]) i := n – 1 medan i ≤ m – 1 gör k := 0 medan k ≤ m – 1 och K[ n – 1 – k ] = M[ i – k ] gör k := k + 1 om k = m returnera i – n + 1 annars i = i + T[M[ i ]] returnerar "Key not found"
Även om det kanske inte är uppenbart, är den värsta körtidseffektiviteten för denna algoritm O( mn ). Lyckligtvis, på texter som är slumpmässiga, är körtidseffektiviteten linjär, O( n/m ) . Detta placerar Horspools algoritm, som använder ingångsförbättring, i en mycket snabbare klass än brute-force-algoritmen för detta problem.
Relaterade begrepp
Inputförbättring används ofta omväxlande med förberäkning och förbearbetning . Även om de är relaterade, finns det flera viktiga skillnader som måste noteras.
- Förberäkning och ingångsförbättring kan ibland användas synonymt. Mer specifikt är förberäkning beräkningen av en given indata innan något annat görs med ingången. Ofta genereras en tabell för att se tillbaka på under själva exekveringen av algoritmen. Ingångsförbättring som beräknar värden och tilldelar dem till element i inmatningen kan klassificeras som förberäkning, men likheterna slutar där. Det finns delar av indataförbättring som inte använder förberäkning och termerna bör inte användas ömsesidigt.
- När man talar om att ändra ingångar, missbrukas ofta förbearbetning. Inom datavetenskap är en förprocessor och förbearbetning helt olika. När förbearbetning används i sammanhang är den vanliga avsikten att skildra konceptet med ingångsförbättring, och inte att använda en förprocessor. Implementering av en förprocessor är konceptet där ett program tar en ingång och bearbetar den till en utdata som helt ska användas av ett annat program. Detta låter som ingångsförbättring, men tillämpningen av förprocessor gäller det generiska programmet som bearbetar källingången för att matas ut i ett format som en kompilator kan läsa och sedan kan kompileras.
- Levitin, Anany (2012). Introduktion till The Design & Analysis of Algorithms (tredje upplagan). Pearson. ISBN 978-0-13-231681-1
- Sebesta, Robert W. (2012). Begrepp för programmeringsspråk (tionde upplagan). Pearson. ISBN 978-0-13-139531-2