Closest string
સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં, સૌથી નજીકની સ્ટ્રિંગ એ એન. પી.-હાર્ડ કોમ્પ્યુટેશનલ સમસ્યા છે, જે ઇનપુટ સ્ટ્રિંગ્સના સમૂહના ભૌમિતિક કેન્દ્રને શોધવાનો પ્રયાસ કરે છે. "કેન્દ્ર" શબ્દને સમજવા માટે, બે શબ્દમાળાઓ વચ્ચેનું અંતર નિર્ધારિત કરવું જરૂરી છે. સામાન્ય રીતે, આ સમસ્યાનો અભ્યાસ હેમિંગ અંતરને ધ્યાનમાં રાખીને કરવામાં આવે છે. ઔપચારિક વ્યાખ્યા વધુ ઔપચારિક રીતે, n લંબાઈ-m શબ્દમાળાઓ s1, s2,., sn આપવામાં આવે છે, સૌથી નજીકની શબ્દમાળા સમસ્યા નવી લંબાઈ-m શબ્દમાળા s માટે શોધે છે જેમ કે d (s, si) ≤ k બધા i માટે, જ્યાં d હેમિંગ અંતર સૂચવે છે, અને જ્યાં k શક્ય તેટલું નાનું છે. સૌથી નજીકની સ્ટ્રિંગ સમસ્યાનું નિર્ણય સમસ્યા સંસ્કરણ, જે NP-પૂર્ણ છે, તેના બદલે k ને અન્ય ઇનપુટ તરીકે લે છે અને પ્રશ્ન કરે છે કે શું તમામ ઇનપુટ સ્ટ્રિંગ્સના હેમિંગ અંતર k ની અંદર કોઈ સ્ટ્રિંગ છે કે કેમ. સૌથી નજીકની સ્ટ્રિંગ સમસ્યાને સામાન્ય 1-કેન્દ્ર સમસ્યાના વિશેષ કેસ તરીકે જોઈ શકાય છે જેમાં તત્વો વચ્ચેનું અંતર હેમિંગ અંતરનો ઉપયોગ કરીને માપવામાં આવે છે. પ્રેરણા બાયોઇન્ફોર્મેટિક્સમાં, સૌથી નજીકની સ્ટ્રિંગ સમસ્યા એ ડીએનએમાં સંકેતો શોધવાની સમસ્યાનું સઘન અભ્યાસ કરેલું પાસું છે. સરળતા અને માહિતીમાં ઘટાડો નજીકના શબ્દમાળાના ઉદાહરણોમાં એવી માહિતી હોઈ શકે છે જે સમસ્યા માટે જરૂરી નથી. અમુક અર્થમાં, નજીકના શબ્દમાળાના સામાન્ય ઇનપુટમાં માહિતી હોય છે, જે સમસ્યાની કઠિનતામાં ફાળો આપતી નથી. ઉદાહરણ તરીકે, જો કેટલાક શબ્દમાળાઓમાં a અક્ષર હોય, પરંતુ કોઈમાં પણ z અક્ષર ન હોય, તો બધાને zs સાથે બદલીને આવશ્યકપણે સમકક્ષ ઉદાહરણ મળશે, એટલે કેઃ સુધારેલા ઉદાહરણના ઉકેલમાંથી, મૂળ ઉકેલ પુનઃસ્થાપિત કરી શકાય છે, અને ઊલટું. ઇનપુટને સામાન્ય બનાવવું જ્યારે સમાન લંબાઈ ધરાવતા તમામ ઇનપુટ શબ્દમાળાઓ એકબીજાની ટોચ પર લખવામાં આવે છે, ત્યારે તેઓ એક મેટ્રિક્સ બનાવે છે. અમુક હરોળના પ્રકારો ઉકેલ માટે આવશ્યકપણે સમાન અસરો ધરાવે છે. ઉદાહરણ તરીકે, એક સ્તંભને એન્ટ્રીઓ (a, a, b) સાથે બીજા સ્તંભ (x, x, y) સાથે બદલવાથી અલગ ઉકેલ સ્ટ્રિંગ તરફ દોરી શકે છે, પરંતુ ઉકેલનીયતાને અસર કરી શકતી નથી, કારણ કે બંને સ્તંભો સમાન માળખું વ્યક્ત કરે છે, એટલે કે. પ્રથમ બે એન્ટ્રીઓ સમાન છે, પરંતુ ત્રીજાથી અલગ છે. ઇનપુટ ઉદાહરણને દરેક સ્તંભમાં, જે અક્ષર સૌથી વધુ વખત a સાથે આવે છે, જે અક્ષર સૌથી વધુ વખત b સાથે આવે છે, અને તેથી આગળ બદલીને સામાન્ય કરી શકાય છે. સામાન્યીકૃત ઉદાહરણનો ઉકેલ જોતાં, મૂળ ઉદાહરણ દરેક સ્તંભમાં તેના મૂળ સંસ્કરણના ઉકેલના અક્ષરોને ફરીથી મેપ કરીને શોધી શકાય છે. સ્તંભોનો ક્રમ સમસ્યાની કઠિનતામાં ફાળો આપતો નથી. તેનો અર્થ એ કે, જો આપણે ચોક્કસ ક્રમચય π અનુસાર તમામ ઇનપુટ સ્ટ્રિંગ્સને ક્રમબદ્ધ કરીએ અને તે સુધારેલા ઉદાહરણ માટે ઉકેલ સ્ટ્રિંગ s મેળવીએ, તો π−1 (s) મૂળ ઉદાહરણનો ઉકેલ હશે. ઉદાહરણ ત્રણ ઇનપુટ સ્ટ્રિંગ્સ uvwx, xuwv અને xvwu સાથેનું ઉદાહરણ આપવામાં આવ્યું છે. આને આ રીતે મેટ્રિક્સ તરીકે લખી શકાય છેઃ પ્રથમ સ્તંભમાં મૂલ્યો (u, x, x) છે. x એ અક્ષર છે જે સૌથી વધુ વખત દેખાય છે, તેથી આપણે તેને a દ્વારા બદલીએ છીએ, અને આપણે નવા પ્રથમ સ્તંભ (b, a, a) ને મેળવીને, b દ્વારા બીજા સૌથી વધુ વારંવારના અક્ષર u ને બદલીએ છીએ. બીજા સ્તંભમાં મૂલ્યો (v, u, v) છે. પ્રથમ સ્તંભ માટે, v ને a દ્વારા બદલવામાં આવે છે અને u ને b દ્વારા બદલવામાં આવે છે, જે નવી બીજી સ્તંભ (a, b, a) મેળવે છે. તમામ કૉલમ સાથે આવું કરવાથી સામાન્યીકૃત ઉદાહરણ મળે છે સામાન્યીકરણમાંથી મેળવેલ ડેટા ઘટાડો ઇનપુટને સામાન્ય બનાવવાથી મૂળાક્ષરનું કદ મહત્તમ ઇનપુટ સ્ટ્રિંગ્સની સંખ્યા સુધી ઘટાડે છે. આ એલ્ગોરિધમ્સ માટે ઉપયોગી હોઈ શકે છે, જેનો ચાલવાનો સમય મૂળાક્ષરના કદ પર આધારિત હોય છે. અંદાજિતતા Li et al. બહુપદી-સમય અંદાજ યોજના વિકસાવવામાં આવી જે મોટા છુપાયેલા સ્થિરાંકોને કારણે વ્યવહારીક રીતે બિનઉપયોગી છે. ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબિલિટી ક્લોસ્ટ સ્ટ્રિંગને હલ કરી શકાય છે, જ્યાં k એ ઇનપુટ સ્ટ્રિંગ્સની સંખ્યા છે, L એ તમામ સ્ટ્રિંગ્સની લંબાઈ છે અને d એ સોલ્યુશન સ્ટ્રિંગથી કોઈપણ ઇનપુટ સ્ટ્રિંગ સુધી ઇચ્છિત મહત્તમ અંતર છે. અન્ય સમસ્યાઓ સાથેના સંબંધો નજીકની સ્ટ્રિંગ એ વધુ સામાન્ય નજીકની સબસ્ટ્રિંગ સમસ્યાનો એક વિશેષ કેસ છે, જે સખત રીતે વધુ મુશ્કેલ છે. જ્યારે સૌથી નજીકની સ્ટ્રિંગ ઘણી રીતે ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબલ હોવાનું બહાર આવે છે, ત્યારે આ પરિમાણોના સંદર્ભમાં સૌથી નજીકની સબસ્ટ્રિંગ W [1]-હાર્ડ છે. સંદર્ભો એન. પી.-સખત સમસ્યાઓ ઔપચારિક ભાષાઓ