در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، ( 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 از راس مبدأ به هر راس سینک یا مقصد ( یک راس با هیچ لبه خروجی ) با نمادهای مشخص شده بر روی هر مسیر در گراف مشخص می شوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می شناسد.
مقایسه با درخت پیشوندی با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، 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 پسوند مشترک نیز به اشتراک گذاشته می شود، برای کلماتی که مجموعه ای از پسوندهای یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه می شود.
