{"entities":{"Q1736492":{"pageid":1747233,"ns":120,"title":"Item:Q1736492","lastrevid":56737464,"modified":"2026-03-19T13:37:12Z","type":"item","id":"Q1736492","labels":{"en":{"language":"en","value":"An algorithm to compute the character access count distribution for pattern matching algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042109"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$C5C32C80-4A7F-45E6-A593-D45FF2514BEB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f13d6ac847f06f174055923d4da69717c424d90f","datavalue":{"value":{"text":"An algorithm to compute the character access count distribution for pattern matching algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736492$2ECA52B7-270F-419A-BA00-DF57013B475C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd8f3d43824d623812734d0b77ba017d5beb369e","datavalue":{"value":"1461.68270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$FD27ABAA-ECA4-48DD-90D3-E33658B3DC1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a67f8bbb067f624449de7b88793b8b83f1468c4","datavalue":{"value":{"entity-type":"item","numeric-id":627198,"id":"Q627198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$9530935B-782D-4486-8F0E-1D5D90DA1B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"75584cb74ae9cca03376fd14670cec28fabcf486","datavalue":{"value":{"entity-type":"item","numeric-id":848953,"id":"Q848953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$46F22F79-ECC1-4D46-89E1-7F3AE9110A82","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$F379CEC9-2EAD-4E1D-B1B4-CBDF06690798","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736492$00429415-2BEB-425C-AECA-7C80377785F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e69a9150d6ca539a0575acec661eab168f988071","datavalue":{"value":"Summary: We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we develop an algorithm that efficiently computes the distribution of a pattern matching algorithm's running time cost (such as the number of text character accesses) for any given pattern in a random text model. Text models range from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide an algorithm to compute the exact distribution of \\textit{differences} in running time cost of two pattern matching algorithms. Methodologically, we use extensions of finite automata which we call \\textit{deterministic arithmetic automata} (DAAs) and \\textit{probabilistic arithmetic automata} (PAAs) [the authors, Lect. Notes Comput. Sci. 5029, 95--106 (2008; Zbl 1143.68440)]. Given an algorithm, a pattern, and a text model, a PAA is constructed from which the sought distributions can be derived using dynamic programming. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly by computing the whole distribution of running time cost. Experimentally, we compare Horspool's algorithm, Backward DAWG Matching, and Backward Oracle Matching on prototypical patterns of short length and provide statistics on the size of minimal DAAs for these computations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$6C434ED5-01B6-4D05-A786-A870DA334A72","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$386CC673-8BE6-46C2-AE0E-B78D6E8627B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$5266A64D-2B3E-44D5-B899-326E1AAAD751","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ffbac49e9a45463d48c51c4e8f42e2ddc06485fd","datavalue":{"value":"7042109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$2D5BBD5B-3025-4165-B7A4-A5FA64CF8100","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2450e02f50939b46b52c3140c8d1d485cebe36e5","datavalue":{"value":"pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$0560994A-37A8-4B45-A821-EAB517CA400B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$13801633-22D8-484F-AD3D-ADE193ADFCA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ac3aa141a5e99f6d4ec0321d581483dfafb5e9","datavalue":{"value":"finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$FC82273D-3D81-4384-ABE7-49D13CE3ECF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1279221fe7735b1b47afd1411b335eca7e3f0e","datavalue":{"value":"minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$6A5DAC90-38AD-41A3-935E-88B18DC97674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2adad61b595f798bd2d2e2bd51f30b27cda6323","datavalue":{"value":"deterministic arithmetic automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$0F3491AA-CD98-4D64-8DAD-4DAD43EDDCD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeef1cf10d75d2a9c1f8066b2bb52de899d28c4d","datavalue":{"value":"probabilistic arithmetic automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736492$75F34702-9A5B-44E0-BE08-4BF0631323B2","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"061ba466c09eb5d6befa3d8838ada31357a9b39a","datavalue":{"value":{"entity-type":"item","numeric-id":13540,"id":"Q13540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$D6B5D5ED-FFDA-4EF3-A2B6-BB2D112D69A7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$DBF34AAF-4400-439C-A0A7-1814342D4776","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"87e85ccfb169802b54713fac586dca1db02e39a7","datavalue":{"value":"https://doi.org/10.3390/a4040285","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736492$311A076E-23FF-469B-B217-EBD52D7F01EE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dec60abeeff09195515f6d15b23b073f8ac9b185","datavalue":{"value":"W2105205612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$95B028A9-097E-46F8-B3CF-879EF03982A6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0502e06127bb0952176f568f1b51be3b38a4a6c4","datavalue":{"value":"Q61704584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$1E225E62-95C2-4E0F-B8E9-4CDF92B7D44E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f139fa5f017a8acd954232dd069b0bbafd7dc0c","datavalue":{"value":{"entity-type":"item","numeric-id":3506945,"id":"Q3506945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$166A90EA-20C3-4E70-8864-B2821B7254C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$CC8C6261-9F48-432A-B1A0-55FAEE4303BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74e200c4f897ac4cb0c5ae9f1bab6477c1d7e3dc","datavalue":{"value":{"entity-type":"item","numeric-id":3090391,"id":"Q3090391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$BDC6C699-6D79-4FB3-A129-69E8A0D7D798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9a0749d00d0ace92b95297f3edf5601b66c86d","datavalue":{"value":{"entity-type":"item","numeric-id":1336956,"id":"Q1336956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$68F06575-B19F-41B5-B971-C0F31A7B01B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8f9358af15d8f62b565873b7623d06421e5a7c6","datavalue":{"value":{"entity-type":"item","numeric-id":4552402,"id":"Q4552402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$A0138643-57AE-4A45-87D3-0AA9CED9851C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b6cdf8a4341932e6667b3e448c1e131a64172bd","datavalue":{"value":{"entity-type":"item","numeric-id":4534878,"id":"Q4534878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$CF53F352-03E2-45CC-B544-8D35426BE98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b876ed32416063d20d3c796956274e45e185955","datavalue":{"value":{"entity-type":"item","numeric-id":3138910,"id":"Q3138910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$52371092-5316-4BC7-AF43-F90112A80F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f131f5b77e8f9e27d37de98ae7ca8b5e90d30ca3","datavalue":{"value":{"entity-type":"item","numeric-id":1190450,"id":"Q1190450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$2B9C240A-6B6E-4926-AE0D-344D1E8531BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df20f54f1682b0374eff4577832a150194db768f","datavalue":{"value":{"entity-type":"item","numeric-id":3122912,"id":"Q3122912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$2032BA52-988A-44CF-B456-E5F16C335E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a88c2b8c6f9c8762ae48406210183cc26dd047f5","datavalue":{"value":{"entity-type":"item","numeric-id":2712578,"id":"Q2712578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$EB328AAD-6D3C-4A5D-B54F-B9C88662A9F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9739d0a4854bf3eb41cba566efafae1868d73df","datavalue":{"value":{"entity-type":"item","numeric-id":5486324,"id":"Q5486324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$2DEAE441-9BDC-4A4B-AD03-7220A225F2BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea9d2ef5c5643ebaaec196ace746972969819e66","datavalue":{"value":{"entity-type":"item","numeric-id":1853502,"id":"Q1853502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$F52492A3-9287-4D94-AFF1-AA4B03994A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63419e2733132317589630cd5683e7d9d74bff7a","datavalue":{"value":{"entity-type":"item","numeric-id":4432973,"id":"Q4432973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$A04C4EB4-8FCA-4ED4-8372-20A3F8C67DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4380e6329d2e0866413d52a27fe328bd8401682e","datavalue":{"value":{"entity-type":"item","numeric-id":5459921,"id":"Q5459921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$3E9BD0E7-1169-43CC-B985-3BB415D293AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5cbae2f30502b5f150485e81fdf89a6d36422e2","datavalue":{"value":{"entity-type":"item","numeric-id":938109,"id":"Q938109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$614A81BC-1571-472E-BE1E-BB8A5D1537A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"488409ca044bbead906b27e3fe77bbcc3609276e","datavalue":{"value":{"entity-type":"item","numeric-id":3564884,"id":"Q3564884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$45533060-68A2-406D-AA04-EF3B2ECD7F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be2ce44bdf80df52f5a97dfe72ac01ea51570a9","datavalue":{"value":{"entity-type":"item","numeric-id":4045961,"id":"Q4045961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$DD8F9FA7-48FA-4167-AA6B-B4ECA650CF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"882c2117b1cca8f4449951c34fa08f6f7ea2f1ad","datavalue":{"value":{"entity-type":"item","numeric-id":1589443,"id":"Q1589443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$503C74FA-BFF5-41DB-92BF-1BA15D8339F8","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"b1ec2b0843e11cdd992e120ed33513e0aeeb05fb","datavalue":{"value":"journals/algorithms/MarschallR11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$8DD0505D-F0C5-4E8D-926F-974E41E15B46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e96b6ef3419130cbbf3cab1fc8eb097ef9ab5dd","datavalue":{"value":"10.3390/A4040285","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736492$59FCEFFA-D615-413F-92ED-5E18C0B7F621","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b471f494f6792423d8851fe970d9bce8e4dd1cef","datavalue":{"value":{"entity-type":"item","numeric-id":3564884,"id":"Q3564884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"246ea561b735e0bcddcb9fc3bda9d522f5a7016e","datavalue":{"value":{"amount":"+0.9100634455680848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736492$553B6AA6-0D1A-40C1-8D97-DFE682DCD8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"150a496b0957f58bd81455294643c056ae38e272","datavalue":{"value":{"entity-type":"item","numeric-id":3122912,"id":"Q3122912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69427379e729d48ba4c9694e941c8fb3330a1b1c","datavalue":{"value":{"amount":"+0.8141812086105347","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736492$76B0F310-AE95-467A-BF17-B301D3C70682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e19277a5d931d6ac50127f82ecfb9acd52900af6","datavalue":{"value":{"entity-type":"item","numeric-id":511153,"id":"Q511153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4763c6e7fbde8cd9ffb833a0af64adcaf694caa4","datavalue":{"value":{"amount":"+0.8050930500030518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736492$A6B8ABC9-1A8B-473F-B16E-6FD4A5881053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de0d9702faa312ee4e925763c0bc851ca966c21c","datavalue":{"value":{"entity-type":"item","numeric-id":3796763,"id":"Q3796763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12aadf12279718aa66de715a9584914d9ab05fa2","datavalue":{"value":{"amount":"+0.7986703515052795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736492$E85AFAA2-45E5-427D-8266-FFF61DB5DD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93fa832400ce79d620ca881e7cabeaac3caec27d","datavalue":{"value":{"entity-type":"item","numeric-id":3506945,"id":"Q3506945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"647017c6a4161b20b7b58022243ec1de6e914a7a","datavalue":{"value":{"amount":"+0.7966489791870117","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736492$A6F2DD90-A773-4A2F-B420-6F3C88430C99","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736492$B9DF82BE-FA15-45B1-8779-ED10E7EE2AA9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736492","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736492"}}}}}