Generalized suffix tree
કોમ્પ્યુટર વિજ્ઞાનમાં, સામાન્યીકૃત પ્રત્યય વૃક્ષ એ શબ્દમાળાઓના સમૂહ માટેનું પ્રત્યય વૃક્ષ છે. કુલ લંબાઈના તારના સમૂહને જોતાં, તે પેટ્રિશિયા વૃક્ષ છે જેમાં તારના તમામ પ્રત્યયો છે. તેનો ઉપયોગ મોટાભાગે બાયોઇન્ફોર્મેટિક્સમાં થાય છે. કાર્યાત્મકતા તે સમય અને અવકાશમાં બનાવી શકાય છે, અને સમયની લંબાઈની સ્ટ્રિંગની તમામ ઘટનાઓને શોધવા માટે તેનો ઉપયોગ કરી શકાય છે, જે એસિમ્પ્ટોટિક રીતે શ્રેષ્ઠ છે (મૂળાક્ષરનું કદ સ્થિર છે એમ ધારીને). આવા વૃક્ષનું નિર્માણ કરતી વખતે, દરેક શબ્દમાળાને એક અનન્ય વર્ણમાલાની બહારના માર્કર પ્રતીક (અથવા શબ્દમાળા) સાથે ગાદીવાળાં કરવો જોઈએ જેથી કોઈ પ્રત્યય બીજાની સબસ્ટ્રિંગ ન હોય તેની ખાતરી કરી શકાય, દરેક પ્રત્યયને એક અનન્ય પર્ણ નોડ દ્વારા રજૂ કરવામાં આવે છે. જીએસટીના નિર્માણ માટેના અલ્ગોરિધમ્સમાં યુકોનનનું અલ્ગોરિધમ (1995) અને મેકક્રાઇટનું અલ્ગોરિધમ (1976) નો સમાવેશ થાય છે. ઉદાહરણ ABAB અને BABA શબ્દમાળાઓ માટેનું પ્રત્યય વૃક્ષ ઉપરની આકૃતિમાં દર્શાવવામાં આવ્યું છે. તેઓ અનન્ય ટર્મિનેટર સ્ટ્રિંગ્સ $0 અને $1 સાથે ગાદીવાળાં છે. લીફ નોડ્સમાં સંખ્યાઓ સ્ટ્રિંગ નંબર અને પ્રારંભિક સ્થિતિ છે. નોંધ લો કે લીફ નોડ્સનો ડાબેથી જમણેનો ટ્રાવર્સલ પ્રત્યયના ક્રમબદ્ધ ક્રમને કેવી રીતે અનુરૂપ છે. ટર્મિનેટર શબ્દમાળાઓ અથવા અનન્ય એકલ પ્રતીકો હોઈ શકે છે. આ ઉદાહરણમાં મૂળમાંથી $પરની ધાર છોડી દેવામાં આવી છે. વૈકલ્પિક સામાન્યીકૃત પ્રત્યય વૃક્ષ બનાવવાનો વિકલ્પ એ છે કે શબ્દમાળાઓને જોડવી, અને પરિણામી શબ્દમાળા માટે નિયમિત પ્રત્યય વૃક્ષ અથવા પ્રત્યય શ્રેણી બનાવવી. જ્યારે શોધ પછી હિટનું મૂલ્યાંકન કરવામાં આવે છે, ત્યારે વૈશ્વિક સ્થિતિને દસ્તાવેજો અને સ્થાનિક સ્થિતિઓમાં કેટલાક અલ્ગોરિધમ અને/અથવા ડેટા સ્ટ્રક્ચર સાથે મેપ કરવામાં આવે છે, જેમ કે દસ્તાવેજોની શરૂઆત/અંતની સ્થિતિમાં દ્વિસંગી શોધ. સંદર્ભો બાહ્ય કડીઓ A C બે શબ્દમાળાઓ માટે સામાન્યીકૃત સફિક્સ ટ્રીનું અમલીકરણ વૃક્ષો (ડેટા સ્ટ્રક્ચર્સ) સબસ્ટ્રિંગ સૂચકાંકો સ્ટ્રિંગ ડેટા સ્ટ્રક્ચર્સ કમ્પ્યુટર વિજ્ઞાન પ્રત્યય