{"entities":{"Q3315039":{"pageid":3325747,"ns":120,"title":"Item:Q3315039","lastrevid":110384336,"modified":"2026-11-16T17:15:33Z","type":"item","id":"Q3315039","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845091"}},"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":"Q3315039$DD594C72-435A-476C-B005-03356E819A92","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f45cf7f7e92b9893a3cfc9148e990f104dba2909","datavalue":{"value":"0532.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3315039$E5A3001A-B263-4502-8BC6-71009DF13B83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9aa4172a39bf9ec948c8d6eb790fa409bd68117f","datavalue":{"value":{"entity-type":"item","numeric-id":294883,"id":"Q294883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3315039$1C0EF5AB-2303-4AC8-8203-055A8729B110","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3315039$15F69546-68B7-4EC0-9C46-B70613030E7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3315039$641D9C7E-C560-4E8C-AE3F-98289CDB4D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3315039$74057BD6-B33D-4E16-B30E-2621A12ED1F8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8285ac096b4963a49b6ac57cfcf2d7982fbf5f9","datavalue":{"value":"3845091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3315039$1A951BB5-D2F3-43D0-9A80-F34D79B57AA4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q3315039$F9BC42B8-3E6C-4B03-B024-C99856BA407E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2deee744dff4cd1b31f0802e93fcce186d7ead3","datavalue":{"value":"evolutionary distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q3315039$1B356544-F5B7-4B5D-AD14-44CD257FC686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bde557def9d4616f22a1529222314886ba2bd870","datavalue":{"value":"string-to-string correction","type":"string"},"datatype":"string"},"type":"statement","id":"Q3315039$0449E4D9-26B7-49C1-B07C-15A290815858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d14f17015cc2709565c880285793cb81bdfd1835","datavalue":{"value":"string matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q3315039$11880DA4-E080-40CC-82ED-3DFDFBB26EAB","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":"Q3315039$01025ED2-92A5-42BA-B964-BED7C1A9A3BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"744ad8d6a7219b62e4684a5f7c1c2af0312b32d9","datavalue":{"value":{"entity-type":"item","numeric-id":4454547,"id":"Q4454547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ba6fb8a917441f4a0d34fbd259e767246639f98","datavalue":{"value":{"amount":"+0.8697762489318848","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":"Q3315039$86DAA6D8-716A-480B-A097-E534DB9FE472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5b12fe73f8e189cfb86ed150ddb389ed9bcaf92","datavalue":{"value":{"entity-type":"item","numeric-id":4250214,"id":"Q4250214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1627b91ae3d6d8dec6820d1149d6175f3d8d0a7","datavalue":{"value":{"amount":"+0.8611072301864624","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":"Q3315039$9AC1FC6C-CA2F-41C9-9620-B989780C2DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49deab15476c54685b893b2a8848978c4ca94e12","datavalue":{"value":{"entity-type":"item","numeric-id":1895867,"id":"Q1895867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5aa1c3e0b5c026fcae27724d111505539cc8284","datavalue":{"value":{"amount":"+0.8586300611495972","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":"Q3315039$7638455F-520E-46DD-BC12-C9496642DFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5a5a4102ed40fecdda865ae52b1b7b49a31904","datavalue":{"value":{"entity-type":"item","numeric-id":2944538,"id":"Q2944538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"652cb7328032d939ea469f2edb49b775019dd8d7","datavalue":{"value":{"amount":"+0.8558386564254761","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":"Q3315039$FD698375-DB1D-4A60-888B-79715F678043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd5f8c7a47258fbc27c1df60e05b1d18fbac014d","datavalue":{"value":{"entity-type":"item","numeric-id":4828999,"id":"Q4828999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dac90fe1457c248088d123f49c4b56b5e9d05bad","datavalue":{"value":{"amount":"+0.8558381199836731","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":"Q3315039$27A5088B-5C68-49A4-8A8A-B185EC556587","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"314a81a168adbab249832ec96f52747703a3d931","datavalue":{"value":"[This article was published in this book announced in this Zbl 0513.00010.] The edit distance between two strings is usually measured as the minimum number of deletions, insertions and changes of symbols needed to transform one string into the other. Also the transposition of two ajacent symbols can be included in the editing operations. This paper gives an improved algorithm for computing the edit distance. For two strings \\(a_ 1a_ 2...a_ m\\) and \\(b_ 1b_ 2...b_ n\\) the algorithm computes the edit distance s as well as the corresponding sequence of editing steps (insertions, deletions, changes, transpositions) in time 0(\\(s\\cdot \\min(m,n))\\) and in space \\(0(s^ 2)\\). If the editing sequence is not needed, the space requirement reduces to 0(s). Given a threshold value t, the algorithm can also be modified to test in time 0(\\(t\\cdot \\min(m,n))\\) and space 0(t) whether the edit distance of the two strings is at most t. For small s, this algorithm significantly improves the well-known dynamic programming method for this problem [see e.g. the paper by \\textit{R. A. Wagner} ad \\textit{M. J. Fischer}, J. Assoc. Comput. Mach. 21, 168-173 (1974; Zbl 0278.68032)], whose time requirement is 0(mn) and space requirement is 0(mn) or 0(min(m,n)) depending on whether or not the editing sequence is needed. Also note that instead of 'edit distance' the terms 'evolutionary distance' and 'string-to-string correction' are sometimes used in the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3315039$2FBB51F2-FDB5-405F-8EF0-5DF5F8207294","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3315039","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3315039"}}}}}