ماشین غیرمدور قطعی متناهی
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (ژوئن ۲۰۱۵) |
 | این مقاله دقیق، کامل و صحیح ترجمه نشده و نیازمند ترجمه به فارسی است. کل یا بخشی از این مقاله به زبانی بهجز زبان فارسی نوشته شدهاست. اگر مقصود ارائهٔ مقاله برای مخاطبان آن زبان است، باید در نسخهای از ویکی‌پدیا به همان زبان نوشته شود (فهرست ویکیپدیاها را ببینید). در غیر این صورت، خواهشمند است ترجمهٔ این مقاله را با توجه به متن اصلی و با رعایت سیاست ویرایش، دستور خط فارسی و برابر سازی به زبان فارسی بهبود دهید و سپس این الگو را از بالای صفحه بردارید. همچنین برای بحثهای مرتبط، مدخل این مقاله در فهرست صفحههای نیازمند ترجمه به فارسی را ببینید. اگر این مقاله به زبان فارسی بازنویسی نشود، تا دو هفتهٔ دیگر نامزد حذف می‌شود و/یا به نسخهٔ زبانی مرتبط ویکی‌پدیا منتقل خواهد شد. اگر شما اخیراً این مقاله را بهعنوان صفحهٔ نیازمند ترجمه برچسب زدهاید، لطفاً عبارت {{جا:هبک-ترجمه به فارسی|1=ماشین غیرمدور قطعی متناهی}} ~~~~را نیز در صفحهٔ بحث نگارنده قرار دهید. |
 | برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (ژوئن ۲۰۱۵) |
 | این مقاله به دلیل مقاله ضعیف است نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (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 به‌طور مستقیم نمی‌تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند، به عنوان مثال تکرار یک کلمه در زبان انگلیسی. با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می‌توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. در آن صورت اطلاعات کمکی می‌تواند در یک آرایه ذخیره می‌شود.
منابع[ویرایش]
- Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), "The smallest automation recognizing the subwords of a text", Theoretical computer science, 40: 31–55, doi:10.1016/0304-3975(85)90157-4
- Appel, Andrew; Jacobsen, Guy (1988), "The World's Fastest Scrabble Program" (PDF), Communications of the ACM. One of the early mentions of the data structure.
- Jansen, Cees J. A.; Boekee, Dick E. (1990), "On the significance of the directed acyclic word graph in cryptology", Advances in Cryptology — AUSCRYPT '90, Lecture Notes in Computer Science, vol. 453, Springer Science+Business Media, pp. 318–326, doi:10.1007/BFb0030372, ISBN 3-540-53000-2.
- Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J. (eds.), Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science, vol. 3340, Springer Science+Business Media, pp. 175–187, ISBN 3-540-24014-4, Zbl 1117٫68454
{{citation}}: Check|zbl=value (help)
پیوند به بیرون[ویرایش]
- 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).