ماشین غیرمدور قطعی متناهی

در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (DAFSA)، یا یک گراف جهت‌دار بدون دور از کلمات(DAWG، هر چند که این نام به ساختمان داده مربوط به توابع به عنوان شاخص پسوند هم اشاره می‌کند) یک ساختارداده است که نشان دهنده مجموعه‌ای از رشته هاست، و اجازه می‌دهد تا برای یک عملیات پرس و جو که امتحان کند که آیا یک رشته داده شده متعلق به مجموعه در زمان متناسب با طول آن هست یا نه. از این جهات، DAFSA بسیار شبیه به یک درخت پیشوندی است، اما با فضای بسیار کارآمد ترو به صرفه تر.

DAFSA یک مورد خاص از یک تشخیص دهنده متناهی است که شبیه به شکل یک گراف بدون دور جهت دار با یک راس مبدأ (یک راس با لبه‌های ورودی)، که در آن هر لبه گراف توسط یک نام یا نماد برچسب خورده است، که در آن هر راس حداکثر یک لبه خروجی برای هر حرف یا نماد را داراست. رشته‌های ارائه شده توسط DAFSA از راس مبدأ به هر راس سینک یا مقصد (یک راس با هیچ لبه خروجی) با نمادهای مشخص شده بر روی هر مسیر در گراف مشخص می‌شوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می‌شناسد.

مقایسه با درخت پیشوندی
با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، DAFSA ممکن است به‌طور قابل توجهی راس کمتر از درخت پیشوندی مرتبط برای رسیدن به راس مقصد استفاده کند. به عنوان مثال، برای چهار کلمه انگلیسی "tap", "taps", "top", and "tops". یک درخت پیشوندی با ۱۱ راس وجود خواهد داشت، یکی برای هر رشته به عنوان یک پیشوند برای این کلمات، یا برای هر کلمه " پایان رشته " برچسب خورده باشد. با این حال، DAFSA می‌تواند این چهار کلمهٔ مشابه را با استفاده از تنها شش راس vi برای i از ۰ تا ۵، و لبه‌های زیر نشان دهد:

یک لبه از V0 به V1 با برچسب "T"، دو لبه از V1 تا V2 با برچسب "A" و " O "، یک لبه از V2 به V3 با برچسب" p "، یک لبه از V3به V4 با برچسب" S "، و لبه‌هایی از V3 و V4 به V5 با برچسب " پایان رشته ". یک مقایسه بین حافظه و قابلیت وجود دارد، زیرا یک DAFSA استاندارد می‌تواند بگوید که یک کلمه در آن وجود دارد یا نه، اما نمی‌توانداطلاعات اضافه‌ای در مورد آن بدهد، در حالی که یک درخت پیشوندی چنین قابلیتی را داراست.

تفاوت اصلی بین DAFSA و درخت پیشوندی حذف افزونگی پسوند و میانوند در ذخیره‌سازی رشته است. درخت پیشوندی به حذف افزونگی پیشوند از همه پیشوندها مشترک بین رشته‌ها می‌پردازد، مانند پزشکان و دکترای که پیشوند دکتر مشترک است. در یک DAFSA پسوند مشترک نیز به اشتراک گذاشته می‌شود، برای کلماتی که مجموعه‌ای از پسوندهای یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه می‌شود.

از آنجا که می‌توان با چندین مسیر به یک گره پایانی در DAFSAرسید ،DAFSA به‌طور مستقیم نمی‌تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند، به عنوان مثال تکرار یک کلمه در زبان انگلیسی. با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می‌توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. در آن صورت اطلاعات کمکی می‌تواند در یک آرایه ذخیره می‌شود.

منابع 

 
 . One of the early mentions of the data structure.
 .

پیوند به بیرون 
 http://pages.pathcom.com/~vadco/dawg.html - JohnPaul Adamovsky teaches how to construct a DAFSA using an array of integers.
 http://pages.pathcom.com/~vadco/cwg.html - JohnPaul Adamovsky teaches how to construct a DAFSA hash function using a novel encoding with multiple integer arrays. This encoding is called the Caroline Word Graph (CWG).

ساختارهای داده‌های رشته‌ای
ماشین متناهی