एल्गोरिदम सबसे लंबे एनाग्राम को खोजने के लिए

Question

मान लें कि हमारे पास लगभग 250,000 शब्द का शब्दकोश है। एल्गोरिदम को 12 अक्षरों को एक सरणी या स्ट्रिंग के रूप में लेना चाहिए और उस शब्द को ढूंढना चाहिए जो एक शब्दकोश से सबसे लंबे शब्द से मेल खाता है।

बेशक, कोई भी हमेशा इसे बलपूर्वक मजबूर कर सकता है, लेकिन मुझे आश्चर्य है कि ऐसा करने का सबसे शानदार तरीका क्या होगा?

PHP के अलावा अन्य भाषाओं का उपयोग करने के उत्तर भी स्वीकार किए जाएंगे यदि वे किसी भी भाषा-विशिष्ट कार्यों को मुख्य समस्या के शॉर्टकट के रूप में उपयोग नहीं करते हैं।

नोट: डेटाबेस डेटाबेस में संग्रहीत हैं, लेकिन मैं उन्हें गति के लिए स्मृति में खींच सकता हूं। हालांकि मुझे यकीन नहीं है कि PHP की अनुक्रमणिका एक MySQL डेटाबेस की तुलना में बेहतर है?

Answer 1

मैं का जवाब की एक थोड़ा संशोधित संस्करण के साथ जाना चाहते हैं the anagram question here

शब्दकोश में प्रत्येक शब्द के लिए, अक्षरों को अक्षर क्रमबद्ध करें। तो "foobar" बन जाता है "abfoor।"

अपने पूर्ण इनपुट, वर्णानुक्रम से क्रमबद्ध के साथ शुरू करें। यदि यह नहीं मिला है, तो एक पत्र हटा दें, फिर से खोज करें। हर पत्र के लिए यह करो। फिर दो अक्षर हटाएं ... और इसी तरह।

सबसे खराब मामला: कोई 'एनाग्राम' बिल्कुल नहीं मिला। आपको सभी संभावित इनपुट संयोजनों का परीक्षण करना होगा, जो आपको लगभग 2^एन लुकअप देगा जहां एन इनपुट वर्णों की संख्या है (आपके उदाहरण में: 12) हालांकि, एल्गोरिदम की गति इस आकार पर निर्भर नहीं है रन टाइम पर शब्दकोश (बेशक, शब्दों को वर्णानुक्रम में क्रमबद्ध करना) जो मेरी राय में सबसे महत्वपूर्ण बात है।

Answer 2

आप सबसे लंबे समय तक मिलता-जुलता शब्द खोजने की कोशिश कर रहे हैं, तो मैं शब्द लंबाई से शब्दकोश सॉर्ट करने के लिए कोशिश कर रहा द्वारा शुरू होगा, तो आप सबसे लंबे समय तक शब्द पर सबसे प्रयास ध्यान केंद्रित कर सकते

Answer 3

मेरा विचार:

स्यूडोकोड:

int_32 letter_mask 
int_32 permutation_match_mask 
if(((letter_mask XOR permutation_match_mask) AND letter_mask) == 0) 
     YOU_HAVE_HIT; 

अच्छी तरह से काम करता है आप lettermask में गैर repetive पत्र है जब, लेकिन आप अधिक पत्र है (जैसा कि आप शायद है) की तुलना में आप leter का विस्तार करने और permutationmatchmask कर सकते हैं

संपादित

एक और विचार

क्रमबद्ध शब्दावली में alphabeticaly आदेश से शब्द।

यदि 12 लेटेरेस हैं और उनमें से सभी अलग हैं, तो बिल्कुल 4095 पॉजिबल कोबेशन्स (केवल योग i = 1-> 12 द्विपक्षीय (12 से अधिक)) (अक्षरों एबीसीडी के लिए, हैं (एबीसीडी, एबीसी , एबीडी, एसीडी, बीसीडी, एबी, एसी, एडी, बीसी, बीडी, सीडी, ए, बी, सी, डी) और जैसा कि मैंने कहा कि 12 अलग-अलग अक्षरों में 40 9 5 हैं और कुछ अक्षर भी कम हैं।

जटिलता 4095 * log2 (250000) क्या aproximetly 75000. खैर यह कोशिश करने के लिए लायक है

प्रत्येक संयोजन पर सटीक खोज के लिए जाओ है।।

Answer 4

आपको प्रत्येक शब्द के हस्ताक्षर की गणना करनी चाहिए, आप इसे केवल एक बार करते हैं और इसे शब्द के साथ अपने डेटाबेस में सहेजते हैं।

तालिका कुछ इस तरह होना चाहिए:

:

word varchar(12), 
    a int, 
    b int, 
    c int, 
    ... 
    w int, 
    z int; 

और z करने के लिए एक से क्षेत्रों के लिए है शब्द में निहित पत्र की संख्या में शामिल हैं, उदाहरण के अनाग्राम के लिए की तरह एक रिकार्ड होता है

:

word, a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z 
anagram, 3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0 

एक बार आप बारह पत्र आप सेट के हस्ताक्षर की गणना और यह का उपयोग इस तरह की एक चयन बनाने के लिए करने के लिए है

select word, length(word) as wordlen 
from dictionary 
where 
a <= 4 and 
b <= 0 and 
c <= 1 and 
d <= 2 and 
e <= 0 and 
f <= 0 and 
.... 
z <= 0 
order by wordlen desc; 

आपके द्वारा निर्धारित पत्र सेट का उपयोग करके बनाए जा सकने वाले सभी शब्द रखने के लिए।

कोई क्रमपरिवर्तन, कोई संयोजन नहीं और हालांकि काम (शब्दकोश संकलित) केवल एक बार और ऑफलाइन किया जाता है।

बस एक और संकेत है, डेटाबेस से पट्टी सभी शब्दों है कि लंबे समय तक बारह से वर्ण

Answer 5

एरिक Lippert लिखा है एक जानकारीपूर्ण blog post अनाग्राम खोज के बारे में कर रहे हैं। उदाहरण सभी सी # का उपयोग करते हैं, लेकिन तकनीक किसी भी भाषा में प्रयोग योग्य है।

एक शब्दकोश में एनाग्राम की कुशलतापूर्वक खोज करने की चाल यह जानना है कि सभी एनाग्रामों में एक ही अक्षर हैं, बस अलग-अलग क्रम में। यदि आप "canonicalize" प्रत्येक शब्द ताकि उसके पत्र अपरकेस और वर्णमाला के क्रम में, फिर देखना हो एक शब्द एक और का विपर्यय शब्द है इस तकनीक के साथ उनके विहित प्रपत्रों

की तुलना के रूप में सरल है, आप आसानी से देख सकते हैं एक हैश टेबल या संतुलित पेड़ से एनाग्राम ऊपर।