Deterministic acyclic finite state automaton
কম্পিউটার বিজ্ঞানে, একটি নির্ধারক অ্যাসাইক্লিক ফাইনাইট স্টেট অটোমেটন (ডিএএফএসএ), যাকে একটি নির্দেশিত অ্যাসাইক্লিক ওয়ার্ড গ্রাফও বলা হয় (ডিএডাব্লুজি; যদিও এই নামটি একটি সম্পর্কিত ডেটা কাঠামোকেও বোঝায় যা একটি প্রত্যয় সূচক হিসাবে কাজ করে) একটি ডেটা স্ট্রাকচার যা স্ট্রিংয়ের একটি সেটকে উপস্থাপন করে এবং একটি ক্যোয়ারি অপারেশনের অনুমতি দেয় যা একটি প্রদত্ত স্ট্রিং তার দৈর্ঘ্যের আনুপাতিক সময়ে সেটের অন্তর্গত কিনা তা পরীক্ষা করে। অ্যালগরিদমগুলি ন্যূনতম রেখে এই জাতীয় অটোমাটা তৈরি এবং রক্ষণাবেক্ষণের জন্য বিদ্যমান। একটি ডি. এ. এফ. এস. এ হল একটি সীমাবদ্ধ অবস্থা শনাক্তকারীর একটি বিশেষ কেস যা একটি একক উৎস শীর্ষ (একটি শীর্ষ যার কোনও আগত প্রান্ত নেই) সহ একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফের রূপ নেয়, যেখানে গ্রাফের প্রতিটি প্রান্তকে একটি অক্ষর বা প্রতীক দ্বারা লেবেল করা হয় এবং যেখানে প্রতিটি শীর্ষে প্রতিটি সম্ভাব্য অক্ষর বা প্রতীকের জন্য সর্বাধিক একটি বহির্গামী প্রান্ত থাকে। ডিএএফএসএ দ্বারা প্রতিনিধিত্ব করা স্ট্রিংগুলি উৎস শীর্ষ থেকে যে কোনও সিঙ্ক শীর্ষে (কোনও বহির্গামী প্রান্ত সহ একটি শীর্ষ) গ্রাফের পথের প্রতীক দ্বারা গঠিত হয়। প্রকৃতপক্ষে, একটি নির্ধারক সীমাবদ্ধ অবস্থা স্বয়ংক্রিয় চক্রাকার হয় যদি এবং শুধুমাত্র যদি এটি স্ট্রিংয়ের একটি সীমাবদ্ধ সেটকে স্বীকৃতি দেয়। একাধিক পথ দিয়ে একই শীর্ষে পৌঁছানোর অনুমতি দিয়ে, একটি ডিএএফএসএ দৃঢ়ভাবে সম্পর্কিত ট্রাই ডেটা কাঠামোর তুলনায় উল্লেখযোগ্যভাবে কম শীর্ষ ব্যবহার করতে পারে। উদাহরণস্বরূপ, চারটি ইংরেজি শব্দ "ট্যাপ", "ট্যাপ", "টপ" এবং "টপ" বিবেচনা করুন। এই চারটি শব্দের জন্য একটি ট্রাইতে 12টি শীর্ষ থাকবে, এই শব্দগুলির মধ্যে একটির উপসর্গ হিসাবে গঠিত প্রতিটি স্ট্রিংয়ের জন্য একটি বা স্ট্রিংয়ের শেষ চিহ্নিতকারী দ্বারা অনুসরণ করা শব্দের জন্য একটি। যাইহোক, একটি ডিএএফএসএ শুধুমাত্র ছয়টি শীর্ষ ব্যবহার করে এই একই চারটি শব্দের প্রতিনিধিত্ব করতে পারে এবং নিম্নলিখিত প্রান্তগুলিঃ "টি" লেবেলযুক্ত v0 থেকে v1 পর্যন্ত একটি প্রান্ত, "এ" এবং "ও" লেবেলযুক্ত v1 থেকে v2 পর্যন্ত দুটি প্রান্ত, "পি" লেবেলযুক্ত v2 থেকে v3 পর্যন্ত একটি প্রান্ত, "এস" লেবেলযুক্ত একটি প্রান্ত v3 থেকে v4 পর্যন্ত এবং স্ট্রিং মার্কারের শেষে লেবেলযুক্ত v3 এবং v4 থেকে v5 পর্যন্ত প্রান্ত। মেমোরি এবং কার্যকারিতার মধ্যে একটি বিনিময় রয়েছে, কারণ একটি আদর্শ ডিএএফএসএ আপনাকে বলতে পারে যে এর মধ্যে কোনও শব্দ বিদ্যমান কিনা, তবে এটি আপনাকে সেই শব্দ সম্পর্কে সহায়ক তথ্যের দিকে নির্দেশ করতে পারে না, যেখানে একটি ট্রাই করতে পারে। ডিএএফএসএ এবং ট্রাই-এর মধ্যে প্রাথমিক পার্থক্য হল স্ট্রিং সংরক্ষণের ক্ষেত্রে প্রত্যয় এবং ইনফিক্স রিডান্ডেন্সি নির্মূল করা। ট্রাই উপসর্গ অপ্রয়োজনীয়তা দূর করে কারণ সমস্ত সাধারণ উপসর্গ স্ট্রিংয়ের মধ্যে ভাগ করা হয়, যেমন ডাক্তার এবং ডক্টরেটের মধ্যে ডাক্তার উপসর্গ ভাগ করা হয়। একটি ডিএএফএসএ-তে সাধারণ প্রত্যয়গুলিও ভাগ করা হয়, যে শব্দগুলির একে অপরের মতো সম্ভাব্য প্রত্যয়গুলির একই সেট রয়েছে। সাধারণ ইংরেজি শব্দের অভিধান সেটের জন্য, এটি প্রধান মেমরি ব্যবহার হ্রাস হিসাবে অনুবাদ করে। যেহেতু একটি ডিএএফএসএর টার্মিনাল নোডে একাধিক পথ দিয়ে পৌঁছানো যায়, তাই একটি ডিএএফএসএ সরাসরি প্রতিটি পথ সম্পর্কিত সহায়ক তথ্য সংরক্ষণ করতে পারে না, যেমন। ইংরেজি ভাষায় একটি শব্দের ফ্রিকোয়েন্সি। যাইহোক, যদি প্রতিটি নোডের জন্য আমরা কাঠামোর সেই বিন্দুর মধ্য দিয়ে অনন্য পথের সংখ্যা সংরক্ষণ করি, তবে আমরা একটি শব্দের সূচক বা তার সূচক দেওয়া একটি শব্দ পুনরুদ্ধার করতে এটি ব্যবহার করতে পারি। সহায়ক তথ্য তারপর একটি অ্যারেতে সংরক্ষণ করা যেতে পারে। রেফারেন্স। তথ্য কাঠামোর প্রাথমিক উল্লেখগুলির মধ্যে একটি। । একটি ওপেন সোর্স পাইথন বাস্তবায়ন। বাহ্যিক লিঙ্ক "ডাইরেক্টেড অ্যাসাইক্লিক ওয়ার্ড গ্রাফ বা ডিএডাব্লুজি"-জন পল অ্যাডামোভস্কি কীভাবে পূর্ণসংখ্যার একটি অ্যারে ব্যবহার করে একটি ডিএএফএসএ তৈরি করতে হয় তা শেখায় () "ক্যারোলিন ওয়ার্ড গ্রাফ বা সিডব্লিউজি"-জন পল অ্যাডামোভস্কি কীভাবে একাধিক পূর্ণসংখ্যা অ্যারে সহ একটি অভিনব এনকোডিং ব্যবহার করে একটি ডিএএফএসএ হ্যাশ ফাংশন তৈরি করতে হয় তা শেখায় () গ্রাফ ডেটা স্ট্রাকচার স্ট্রিং ডেটা স্ট্রাকচার সীমাবদ্ধ স্বয়ংক্রিয়