Deterministic acyclic finite state automaton
کمپیوٹر سائنس میں، ایک ڈیٹرمینیسٹک ایسائکلک فائنیٹ اسٹیٹ آٹومیٹن (ڈی اے ایف ایس اے)، جسے ڈائریکٹڈ ایسائکلک ورڈ گراف (ڈی اے ڈبلیو جی) بھی کہا جاتا ہے ؛ اگرچہ یہ نام ایک متعلقہ ڈیٹا ڈھانچے سے بھی مراد ہے جو ایک لاحقہ انڈیکس کے طور پر کام کرتا ہے) ایک ڈیٹا ڈھانچہ ہے جو سٹرنگ کے ایک سیٹ کی نمائندگی کرتا ہے، اور ایک استفسار آپریشن کی اجازت دیتا ہے جو اس بات کی جانچ کرتا ہے کہ آیا دی گئی سٹرنگ اس کی لمبائی کے متناسب وقت میں سیٹ سے تعلق رکھتی ہے یا نہیں۔ الگورتھم اس طرح کے آٹومیٹا کی تعمیر اور برقرار رکھنے کے لیے موجود ہیں، جبکہ انہیں کم سے کم رکھتے ہیں۔ ڈی اے ایف ایس اے ایک محدود اسٹیٹ ریکگنیزر کا ایک خاص معاملہ ہے جو ایک واحد ماخذ ورٹیکس (ایک ورٹیکس جس میں کوئی آنے والے کنارے نہیں ہیں) کے ساتھ ایک ڈائریکٹڈ ایسائکلک گراف کی شکل اختیار کرتا ہے، جس میں گراف کے ہر کنارے کو ایک حرف یا علامت سے لیبل کیا جاتا ہے، اور جس میں ہر ورٹیکس میں ہر ممکنہ حرف یا علامت کے لیے زیادہ سے زیادہ ایک باہر جانے والا کنارے ہوتا ہے۔ ڈی اے ایف ایس اے کے ذریعہ پیش کردہ تار گراف میں راستوں پر موجود علامتوں کے ذریعہ تشکیل پاتے ہیں جو ماخذ ورٹیکس سے کسی بھی سنک ورٹیکس (ایک ورٹیکس جس میں کوئی باہر جانے والے کنارے نہیں ہوتے ہیں) تک ہوتے ہیں۔ در حقیقت، ایک تعیناتی محدود حالت آٹومیٹن اس صورت میں اور صرف اس صورت میں چکنا ہوتا ہے جب وہ تاروں کے ایک محدود سیٹ کو پہچانتا ہے۔ ایک ہی عمودی حصوں کو متعدد راستوں سے پہنچنے کی اجازت دینے سے، ڈی اے ایف ایس اے مضبوطی سے متعلق ٹرائی ڈیٹا ڈھانچے کے مقابلے میں نمایاں طور پر کم عمودی حصوں کا استعمال کر سکتا ہے۔ مثال کے طور پر، چار انگریزی الفاظ "ٹیپ"، "ٹیپس"، "ٹاپ"، اور "ٹاپس" پر غور کریں۔ ان چار الفاظ کے لیے ایک تثلیث میں 12 عمودی ہوتے ہیں، ان الفاظ میں سے کسی ایک کے سابقہ کے طور پر بنائے گئے ہر ایک تار کے لیے، یا ان الفاظ میں سے کسی ایک کے لیے جس کے بعد تار کے آخر کا نشان ہوتا ہے۔ تاہم، ایک ڈی اے ایف ایس اے ان ہی چار الفاظ کی نمائندگی کر سکتا ہے جس میں صرف چھ عمودی vi کا استعمال کرتے ہوئے 0 ≤ i ≤ 5، اور مندرجہ ذیل کنارے: v0 سے v1 تک کا ایک کنارہ جس پر "t" کا لیبل لگا ہوا ہے، v1 سے v2 تک کے دو کناروں پر "a" اور "o" کا لیبل لگا ہوا ہے، v2 سے v3 تک کا ایک کنارہ جس پر "p" کا لیبل لگا ہوا ہے، ایک کنارہ v3 سے v4 پر "s" کا لیبل لگا ہوا ہے، اور v3 اور v4 سے v5 تک کے کناروں پر اینڈ آف سٹرنگ مارکر کا لیبل لگا ہوا ہے۔ میموری اور فعالیت کے درمیان ایک تغیر ہے، کیونکہ ایک معیاری ڈی اے ایف ایس اے آپ کو بتا سکتا ہے کہ آیا اس کے اندر کوئی لفظ موجود ہے، لیکن یہ آپ کو اس لفظ کے بارے میں معاون معلومات کی طرف اشارہ نہیں کر سکتا، جبکہ ایک ٹرائی کر سکتا ہے۔ ڈی اے ایف ایس اے اور ٹرائی کے درمیان بنیادی فرق تاروں کو ذخیرہ کرنے میں لاحقہ اور انفکس بے کار پن کا خاتمہ ہے۔ ٹرائی پریفیکس ریڈنڈنسی کو ختم کرتا ہے کیونکہ تمام عام پریفیکس تاروں کے درمیان مشترک ہوتے ہیں، جیسے کہ ڈاکٹروں اور ڈاکٹریٹ کے درمیان ڈاکٹر پریفیکس مشترک ہوتا ہے۔ ڈی اے ایف ایس اے میں عام لاحقہ بھی مشترکہ ہوتے ہیں، ان الفاظ کے لیے جن میں ایک دوسرے کی طرح ممکنہ لاحقہ کا ایک ہی مجموعہ ہوتا ہے۔ عام انگریزی الفاظ کے ڈکشنری سیٹوں کے لیے، یہ میموری کے استعمال میں بڑی کمی میں ترجمہ کرتا ہے۔ چونکہ ڈی اے ایف ایس اے کے ٹرمینل نوڈس تک متعدد راستوں سے پہنچا جا سکتا ہے، اس لیے ڈی اے ایف ایس اے ہر راستے سے متعلق معاون معلومات کو براہ راست ذخیرہ نہیں کر سکتا، جیسے۔ انگریزی زبان میں کسی لفظ کی تعدد۔ تاہم، اگر ہر نوڈ کے لیے ہم ساخت میں اس نقطہ کے ذریعے منفرد راستوں کی تعداد کو محفوظ کرتے ہیں، تو ہم اسے کسی لفظ کے اشاریہ، یا اس کے اشاریہ کو دیئے گئے لفظ کو بازیافت کرنے کے لیے استعمال کر سکتے ہیں۔ معاون معلومات کو پھر ایک صف میں محفوظ کیا جا سکتا ہے۔ حوالہ جات۔ ڈیٹا ڈھانچے کے ابتدائی ذکر میں سے ایک۔ ۔ ایک اوپن سورس ازگر کا نفاذ۔ بیرونی لنکس "ڈائریکٹڈ ایسائکلک ورڈ گراف یا ڈی اے ڈبلیو جی"-جان پال ایڈمووسکی سکھاتا ہے کہ انٹیجرز کی ایک صف کا استعمال کرتے ہوئے ڈی اے ایف ایس اے کی تعمیر کیسے کی جائے () "کیرولین ورڈ گراف یا سی ڈبلیو جی"-جان پال ایڈمووسکی سکھاتا ہے کہ متعدد انٹیجر صفوں کے ساتھ ایک ناول انکوڈنگ کا استعمال کرتے ہوئے ڈی اے ایف ایس اے ہیش فنکشن کیسے بنایا جائے () گراف ڈیٹا ڈھانچے سٹرنگ ڈیٹا ڈھانچے فائنائٹ آٹومیٹا