Deterministic acyclic finite state automaton
કોમ્પ્યુટર વિજ્ઞાનમાં, એક નિર્ધારક એસાયક્લિક ફાઇનાઇટ સ્ટેટ ઓટોમેટન (ડીએએફએસએ), જેને નિર્દેશિત એસાયક્લિક વર્ડ ગ્રાફ (ડીએડબલ્યુજી) પણ કહેવામાં આવે છે; જોકે તે નામ સંબંધિત ડેટા સ્ટ્રક્ચરનો પણ ઉલ્લેખ કરે છે જે પ્રત્યય અનુક્રમણિકા તરીકે કાર્ય કરે છે) એક ડેટા સ્ટ્રક્ચર છે જે શબ્દમાળાઓના સમૂહને રજૂ કરે છે, અને ક્વેરી ઓપરેશન માટે પરવાનગી આપે છે જે પરીક્ષણ કરે છે કે આપેલ શબ્દમાળા તેની લંબાઈના પ્રમાણમાં સમયના સમૂહ સાથે સંબંધિત છે કે કેમ. આવા ઓટોમેટા બનાવવા અને જાળવવા માટે અલ્ગોરિધમ્સ અસ્તિત્વ ધરાવે છે, જ્યારે તેમને ન્યૂનતમ રાખે છે. ડીએએફએસએ એ મર્યાદિત સ્થિતિ ઓળખકર્તાનો એક વિશેષ કેસ છે જે એક જ સ્રોત શિરોબિંદુ (કોઈ આવનારી ધાર વિનાનું શિરોબિંદુ) સાથે નિર્દેશિત ચક્રીય આલેખનનું સ્વરૂપ લે છે, જેમાં આલેખનની દરેક ધારને અક્ષર અથવા પ્રતીક દ્વારા લેબલ કરવામાં આવે છે, અને જેમાં દરેક શિરોબિંદુ દરેક સંભવિત અક્ષર અથવા પ્રતીક માટે મહત્તમ એક આઉટગોઇંગ ધાર ધરાવે છે. ડી. એ. એફ. એસ. એ. દ્વારા રજૂ કરાયેલ શબ્દમાળાઓ ગ્રાફમાં સ્ત્રોત શિરોબિંદુથી કોઈપણ સિંક શિરોબિંદુ (કોઈ બહારની ધાર વિનાનું શિરોબિંદુ) સુધીના માર્ગો પરના પ્રતીકો દ્વારા રચાય છે. હકીકતમાં, એક નિર્ધારક મર્યાદિત સ્થિતિ સ્વચાલિત ચક્રીય હોય છે જો અને માત્ર ત્યારે જ જો તે શબ્દમાળાઓના મર્યાદિત સમૂહને ઓળખે. સમાન શિરોબિંદુઓને બહુવિધ માર્ગો દ્વારા પહોંચવાની મંજૂરી આપીને, ડીએએફએસએ મજબૂત રીતે સંબંધિત ટ્રાઇ ડેટા સ્ટ્રક્ચર કરતાં નોંધપાત્ર રીતે ઓછા શિરોબિંદુઓનો ઉપયોગ કરી શકે છે. ઉદાહરણ તરીકે, ચાર અંગ્રેજી શબ્દો "ટેપ", "ટેપ", "ટોપ" અને "ટોપ" નો વિચાર કરો. તે ચાર શબ્દોની ત્રિપુટીમાં 12 શિરોબિંદુઓ હશે, આમાંથી કોઈ એક શબ્દના ઉપસર્ગ તરીકે રચાયેલા દરેક શબ્દમાળા માટે અથવા શબ્દમાળાના અંત માર્કર દ્વારા અનુસરવામાં આવતા શબ્દોમાંથી એક માટે. જો કે, ડીએએફએસએ 0 ≤ i ≤ 5 માટે માત્ર છ શિરોબિંદુઓ vi નો ઉપયોગ કરીને આ જ ચાર શબ્દોનું પ્રતિનિધિત્વ કરી શકે છે, અને નીચેની ધારઃ "t" લેબલવાળા v0 થી v1 સુધીની ધાર, "a" અને "o" લેબલવાળા v1 થી v2 સુધીની બે ધાર, "p" લેબલવાળા v2 થી v3 સુધીની ધાર, "s" લેબલવાળા v3 થી v4 સુધીની ધાર, અને એન્ડ-ઓફ-સ્ટ્રિંગ માર્કર સાથે લેબલ થયેલ v3 અને v4 થી v5 સુધીની ધાર. મેમરી અને કાર્યક્ષમતા વચ્ચે ટ્રેડઓફ છે, કારણ કે પ્રમાણભૂત ડીએએફએસએ તમને કહી શકે છે કે તેમાં કોઈ શબ્દ અસ્તિત્વમાં છે કે નહીં, પરંતુ તે તમને તે શબ્દ વિશે સહાયક માહિતી તરફ નિર્દેશ કરી શકતો નથી, જ્યારે કે ટ્રાઇ કરી શકે છે. ડી. એ. એફ. એસ. એ. અને ટ્રાઇ વચ્ચેનો પ્રાથમિક તફાવત એ છે કે સ્ટ્રિંગ્સ સંગ્રહિત કરવામાં પ્રત્યય અને ઇન્ફિક્સ રીડન્ડન્સીને દૂર કરવી. ટ્રાઇ ઉપસર્ગ અતિરેકને દૂર કરે છે કારણ કે તમામ સામાન્ય ઉપસર્ગો શબ્દમાળાઓ વચ્ચે વહેંચાયેલા હોય છે, જેમ કે ડોકટરો અને ડોક્ટરેટ વચ્ચે ડૉક્ટર ઉપસર્ગ વહેંચાયેલું હોય છે. ડી. એ. એફ. એસ. એ. માં સામાન્ય પ્રત્યયો પણ વહેંચવામાં આવે છે, જે શબ્દો એકબીજા જેવા સંભવિત પ્રત્યયોના સમાન સમૂહ ધરાવે છે. સામાન્ય અંગ્રેજી શબ્દોના શબ્દકોશ સમૂહો માટે, આ મુખ્ય મેમરી વપરાશમાં ઘટાડામાં અનુવાદ કરે છે. કારણ કે ડી. એ. એફ. એસ. એ. ના અંતિમ નોડ્સ બહુવિધ માર્ગો દ્વારા પહોંચી શકાય છે, ડી. એ. એફ. એસ. એ. દરેક માર્ગને લગતી સહાયક માહિતીને સીધી સંગ્રહિત કરી શકતું નથી, દા. ત. અંગ્રેજી ભાષામાં શબ્દની આવૃત્તિ. જો કે, જો દરેક નોડ માટે આપણે માળખામાં તે બિંદુ દ્વારા અનન્ય પાથની સંખ્યા સંગ્રહિત કરીએ, તો આપણે તેનો ઉપયોગ શબ્દની અનુક્રમણિકા અથવા તેની અનુક્રમણિકા આપવામાં આવેલા શબ્દને પુનઃપ્રાપ્ત કરવા માટે કરી શકીએ છીએ. સહાયક માહિતી પછી એરેમાં સંગ્રહિત કરી શકાય છે. સંદર્ભો. ડેટા સ્ટ્રક્ચરના પ્રારંભિક ઉલ્લેખમાંથી એક. . ઓપન સોર્સ પાયથોન અમલીકરણ. બાહ્ય કડીઓ "ડિરેક્ટેડ એસાયક્લિક વર્ડ ગ્રાફ અથવા ડીએડબલ્યુજી"-જ્હોનપોલ એડમોવ્સ્કી પૂર્ણાંકોની શ્રેણીનો ઉપયોગ કરીને ડીએએફએસએ કેવી રીતે બનાવવું તે શીખવે છે () "કેરોલિન વર્ડ ગ્રાફ અથવા સીડબ્લ્યુજી"-જ્હોનપોલ એડમોવ્સ્કી શીખવે છે કે કેવી રીતે બહુવિધ પૂર્ણાંક એરે સાથે નવીન એન્કોડિંગનો ઉપયોગ કરીને ડીએએફએસએ હેશ ફંક્શનનું નિર્માણ કરવું () ગ્રાફ ડેટા સ્ટ્રક્ચર્સ સ્ટ્રિંગ ડેટા સ્ટ્રક્ચર્સ ફાઈનાઇટ ઓટોમેટા