[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/6038#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/6038","headline":"LZ77  &#8211; \u30a6\u30a3\u30ad\u30da\u30c7\u30a3\u30a2","name":"LZ77  &#8211; \u30a6\u30a3\u30ad\u30da\u30c7\u30a3\u30a2","description":"before-content-x4 LZ77 \uff08Lempel-Ziv 77\uff09 [\u521d\u3081] 1977\u5e74\u306bAbraham Lempel\u3068Jacob Ziv\u306b\u3088\u3063\u3066\u516c\u958b\u3055\u308c\u305f\u30c7\u30fc\u30bf\u5727\u7e2e\u306e\u30ed\u30b9\u30ec\u30b9\u624b\u9806\u3067\u3059\u3002 \u3053\u308c\u306f\u3001\u30c7\u30fc\u30bf\u30ec\u30b3\u30fc\u30c9\u3067\u30c7\u30fc\u30bf\u306e\u30b7\u30fc\u30b1\u30f3\u30b9\u5168\u4f53\u304c\u6570\u56de\u767a\u751f\u3059\u308b\u306e\u3092\u521d\u3081\u3066\u6d3b\u7528\u3059\u308b\u8f9e\u66f8\u30d9\u30fc\u30b9\u306e\u624b\u9806\u3067\u3059\u3002\u4ee5\u524d\u306e\u624b\u9806\uff08Huffman Coding\u3084Shannon Fano\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u306a\u3069\uff09\u3067\u306f\u3001\u500b\u3005\u306e\u6587\u5b57\u306e\u983b\u5ea6\u306e\u307f\u304c\u4f7f\u7528\u3055\u308c\u307e\u3057\u305f\uff08\u30a8\u30f3\u30c8\u30ed\u30d4\u30fc\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u3082\u53c2\u7167\uff09\u3002 LZ77\u3082\u6700\u521d\u306eLZ\u30d7\u30ed\u30bb\u30b9\u306b\u306a\u308a\u307e\u3059 LZ1 \u547c\u3073\u51fa\u3055\u308c\u307e\u3057\u305f\u3002 after-content-x4 \u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306eLZ77\u56e0\u5b50\u5316 \u30d0\u30c4 {displaystyle x} \u7a7a\u3067\u306a\u3044\u6587\u5b57\u5217\u30c1\u30a7\u30fc\u30f3\u3078\u306e\u5206\u89e3\u3067\u3059","datePublished":"2022-09-04","dateModified":"2022-09-04","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/author\/lordneo#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/author\/lordneo","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/e\/ea\/Disambig-dark.svg\/25px-Disambig-dark.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/e\/ea\/Disambig-dark.svg\/25px-Disambig-dark.svg.png","height":"19","width":"25"},"url":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/6038","wordCount":11848,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4LZ77  \uff08Lempel-Ziv 77\uff09 [\u521d\u3081] 1977\u5e74\u306bAbraham Lempel\u3068Jacob Ziv\u306b\u3088\u3063\u3066\u516c\u958b\u3055\u308c\u305f\u30c7\u30fc\u30bf\u5727\u7e2e\u306e\u30ed\u30b9\u30ec\u30b9\u624b\u9806\u3067\u3059\u3002\u3053\u308c\u306f\u3001\u30c7\u30fc\u30bf\u30ec\u30b3\u30fc\u30c9\u3067\u30c7\u30fc\u30bf\u306e\u30b7\u30fc\u30b1\u30f3\u30b9\u5168\u4f53\u304c\u6570\u56de\u767a\u751f\u3059\u308b\u306e\u3092\u521d\u3081\u3066\u6d3b\u7528\u3059\u308b\u8f9e\u66f8\u30d9\u30fc\u30b9\u306e\u624b\u9806\u3067\u3059\u3002\u4ee5\u524d\u306e\u624b\u9806\uff08Huffman Coding\u3084Shannon Fano\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u306a\u3069\uff09\u3067\u306f\u3001\u500b\u3005\u306e\u6587\u5b57\u306e\u983b\u5ea6\u306e\u307f\u304c\u4f7f\u7528\u3055\u308c\u307e\u3057\u305f\uff08\u30a8\u30f3\u30c8\u30ed\u30d4\u30fc\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u3082\u53c2\u7167\uff09\u3002 LZ77\u3082\u6700\u521d\u306eLZ\u30d7\u30ed\u30bb\u30b9\u306b\u306a\u308a\u307e\u3059 LZ1 \u547c\u3073\u51fa\u3055\u308c\u307e\u3057\u305f\u3002        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306eLZ77\u56e0\u5b50\u5316 \u30d0\u30c4 {displaystyle x} \u7a7a\u3067\u306a\u3044\u6587\u5b57\u5217\u30c1\u30a7\u30fc\u30f3\u3078\u306e\u5206\u89e3\u3067\u3059        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\u306e \u521d\u3081 \u3001 \u306e 2 \u3001 &#8230; \u3001 \u306e k {displaystyle w_ {1}\u3001w_ {2}\u3001ldots\u3001w_ {k}} \u3001 \u3068\u306a\u308b\u3053\u3068\u306b\u3088\u3063\u3066 [2] \u30d0\u30c4 = \u306e 1\u306e 2\u22ef \u306e k{displaystyle x = w_ {1} w_ {2} cdots w_ {k}} \u3068 \u305d\u308c\u305e\u308c\u306e\u305f\u3081 \u306e j{displaystyle w_ {j}} \u3068 \u521d\u3081 \u2264 j \u2264 k {displaystyle 1leq k} \u8a72\u5f53\u3059\u308b\uff1a \u500b\u3005\u306e\u6587\u5b57\u5217 \u306e j {displaystyle w_ {j}} \u306a\u308b \u8981\u56e0 \u307e\u305f \u30d5\u30ec\u30fc\u30ba \u5c02\u7528\u3002 \u5b9a\u7fa9\u304b\u3089\u76f4\u63a5\u5c0e\u304d\u51fa\u3059\u3053\u3068\u304c\u3067\u304d\u307e\u3059        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\u306e \u521d\u3081 = \u30d0\u30c4 [ \u521d\u3081 ] {displaystyle w_ {1} = x [1]} \u306f\u3002\u8aac\u660e\u3055\u308c\u305f \u30d0\u30c4 [ \u79c1 &#8230; j ] {displaystyle x [idots j]} \u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3 \u30d0\u30c4 {displaystyle x} \u305d\u308c\u306f\u4f4d\u7f6e\u304b\u3089 \u79c1 {displaystyle i} \u3059\u3079\u3066\u306e\u6587\u5b57 \u30d0\u30c4 {displaystyle x} \u30dd\u30b8\u30b7\u30e7\u30f3\u307e\u3067\u306e\u3082\u306e\u307e\u3067 j {displaystyle j} \u542b\u3080\u3002 \u30d0\u30c4 [ \u79c1 ] {displaystyle x [i]} \u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306e\u7565\u8a9e\u3067\u3059 \u30d0\u30c4 [ \u79c1 &#8230; \u79c1 ] {displaystyle x [idots i]} \u3002 LZ77\u5727\u7e2e\u3092\u8a08\u7b97\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u30a2\u30a4\u30c7\u30a2\u306f\u3001\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306e\u3059\u3067\u306b\u51e6\u7406\u3055\u308c\u305f\u30d7\u30ec\u30d5\u30a3\u30c3\u30af\u30b9\u3092\u8f9e\u66f8\u3068\u3057\u3066\u4f7f\u7528\u3059\u308b\u3053\u3068\u3067\u3059\u3002\u5b9f\u88c5\u306e\u305f\u3081\u306b\u3001\u3053\u306e\u8f9e\u66f8\u306e\u30b5\u30a4\u30ba\u306f\u3001\u691c\u7d22\u671f\u9593\u3092\u5236\u9650\u3059\u308b\u305f\u3081\u306b\u5b9f\u969b\u306b\u306f\u5236\u9650\u3055\u308c\u3066\u3044\u307e\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u901a\u5e38\u306f\u30b9\u30e9\u30a4\u30c9\u7a93\u3067\u3059\u3002 \u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6 \uff09\u4f7f\u7528\u3055\u308c\u3001\u8003\u616e\u3055\u308c\u308b\u8f9e\u66f8\u3068\u30c6\u30ad\u30b9\u30c8\u306e\u629c\u7c8b\u306e\u4e21\u65b9\u3092\u5236\u9650\u3057\u307e\u3059\uff08\u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc\uff09\u3002\u5727\u7e2e\u6587\u5b57\u306f\u3001\u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc\u304b\u3089\u8f9e\u66f8\u306b\u5f90\u3005\u306b\u79fb\u52d5\u3055\u308c\u307e\u3059\u3002\u5b9f\u969b\u306b\u306f\u3001\u8f9e\u66f8\u306e\u30d0\u30c3\u30d5\u30a1\u306b\u306f\u6570\u5343\u6587\u5b57\u304c\u542b\u307e\u308c\u3066\u304a\u308a\u3001\u30cd\u30c3\u30af\u30e9\u30a4\u30f3\u306e\u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc\u306b\u306f\u7d04100\u6587\u5b57\uff08\u5834\u5408\u306b\u3088\u3063\u3066\u306f\u5c11\u306a\u3044\u5834\u5408\u304c\u3042\u308a\u307e\u3059\uff09\u304c\u542b\u307e\u308c\u3066\u3044\u307e\u3059\u3002 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u5143\u306e\u30c6\u30ad\u30b9\u30c8\u3092\u56de\u5fa9\u3067\u304d\u308b\u4e00\u9023\u306e\u30c8\u30ea\u30d7\u30ec\u30c3\u30c8\u3092\u4f5c\u6210\u3057\u307e\u3059\u3002\u8981\u56e0\u306e\u30c8\u30ea\u30d7\u30eb \u306e j {displaystyle w_ {j}} \u5f62\u304c\u3042\u308a\u307e\u3059 \uff08 p o s \u3001 l \u305d\u3046\u3067\u3059 n \u3001 l \uff09\uff09 {displaystyle\uff08pos\u3001len\u3001lambda\uff09} \u3001\u305d\u308c\u306b\u3088\u3063\u3066 \u8f9e\u66f8\u306b\u30d0\u30c3\u30d5\u30a1\u30fc\u3092\u4f7f\u7528\u3059\u308b\u5834\u5408\u3001 p o s {displaystyle pos} \u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306f\u3001\u30d0\u30c3\u30d5\u30a1\u306e\u5de6\u7aef\u307e\u305f\u306f\u53f3\u7aef\u306b\u6bd4\u3079\u3066\u7406\u89e3\u3055\u308c\u307e\u3059\uff08\u5b9f\u88c5\u306b\u3088\u3063\u3066\u7570\u306a\u308b\u5834\u5408\u304c\u3042\u308a\u307e\u3059\uff09\u3001\u65b0\u3057\u3044\u6587\u5b57\u3092\u4f7f\u7528\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059 \uff08 0 \u3001 0 \u3001 l \uff09\uff09 {displaystyle\uff080,0\u3001lambda\uff09} \u7d39\u4ecb\u3055\u308c\u307e\u3059\u3002\u5727\u7e2e\u306e\u51fa\u529b\u5f62\u5f0f\u306b\u3088\u308a\u3001\u8f9e\u66f8\u3092\u660e\u793a\u7684\u306b\u4fdd\u5b58\u305b\u305a\u306b\u30c6\u30ad\u30b9\u30c8\u3092\u518d\u69cb\u7bc9\u3067\u304d\u307e\u3059\u3002 Table of Contents\u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u4f8b [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u5b9f\u884c\u6642\u9593\u5206\u6790 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u9577\u6240\u3068\u77ed\u6240 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u4f8b [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u5b9f\u884c\u6642\u9593\u5206\u6790 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u95a2\u9023\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u64ec\u4f3c\u30b3\u30fc\u30c9\u306f\u3001\u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u3092\u4f7f\u7528\u3057\u305fLZ77\u5727\u7e2e\u30b5\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8907\u88fd\u3067\u3059\u3002  \u305d\u306e\u9593    \u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc  \u3044\u3044\u3048  \u30d5\u30a1\u30a4\u30eb  \u306f ;  \u3059\u308b  \u691c\u7d22  r \u00fc CKW \u00e4 RTS    \u306e \u5f7c rterbuch  \u5f8c    l \u00e4 \u9f3b  \u00fc \u4e00\u8cab\u6027\u306e\u3042\u308b  \u5f26  \u3068  \u306b  \u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc ;  \u3082\u3057\u3082  \u4e00  \u00fc \u53c2\u7167  \u306a\u308a\u307e\u3057\u305f  \u898b\u3064\u304b\u3063\u305f ;  \u305d\u308c\u304b\u3089  \u30ae\u30d6    \u30c8\u30ea\u30d7\u30eb  \uff08 \u5b50\u5b6b  \u306e\u305f\u3081\u306b  \u30e9\u30f3\u30c9  \u306e  \u306e \u5f7c rterbuch \u3001  l \u00e4 \u306b    \u898b\u3064\u304b\u3063\u305f  \u5f26 \u3001  \u521d\u3081  \u3044\u3044\u3048  \u00fc \u4e00\u8cab\u6027\u306e\u3042\u308b  \u30b5\u30a4\u30f3  out  \u306b  \u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc \uff09\uff09  out ;  \u5ef6\u671f    \u7a93  \u4e00    l \u00e4 \u306b + \u521d\u3081 ;  \u305d\u308c\u4ee5\u5916  \u30ae\u30d6    \u30c8\u30ea\u30d7\u30eb  \uff08 0 \u3001  0 \u3001  \u521d\u3081  \u30b5\u30a4\u30f3  \u306e\u4e2d\u306b  \u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc \uff09\uff09  out ;  \u5ef6\u671f    \u7a93  \u4e00  \u521d\u3081 ;  \u7d42\u308f\u308a  \u3082\u3057\u3082  \u7d42\u308f\u308a  \u305d\u306e\u9593  \u4f8b [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] LZ77\u56e0\u6570\u5206\u89e3\u306e\u8a08\u7b97\u306f\u3001\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306b\u57fa\u3065\u3044\u3066\u3044\u307e\u3059 AACTA\u306e\u4e71\u7528 \u8aac\u660e\u3057\u307e\u3059\u3002 \u3053\u306e\u8868\u306f\u3001\u9577\u305512\u306e\u8f9e\u66f8\u3068\u9577\u305510\u306e\u30d7\u30ec\u30d3\u30e5\u30fc\u30d0\u30c3\u30d5\u30a1\u30fc\uff080\u304b\u30899\u306e\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\uff09\u3092\u4f7f\u7528\u3057\u305fLZ77\u56e0\u6570\u5206\u89e3\u306e\u8a08\u7b97\u3092\u793a\u3057\u3066\u3044\u307e\u3059\u3002\u53f3\u306e\u5217\u3067\u306f\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u51fa\u529b\uff080\u30010\u3001 a \uff09\u3001\uff081\u30011\u3001 c \uff09\u3001\uff083\u30014\u3001 b \uff09\u3001\uff083\u30013\u3001 a \uff09\u304a\u3088\u3073\uff0812\u30013\u3001 \u7d42\u308f\u308a \uff09\u3002\u4f4d\u7f6e\u306f\u8f9e\u66f8\u306e\u53f3\u7aef\u306b\u5bfe\u3057\u3066\u4e0e\u3048\u3089\u308c\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u30c7\u30b3\u30fc\u30c9\u6642\u306b\u540c\u3058\u65b9\u6cd5\u3067\u884c\u3046\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002 \u30d0\u30c3\u30d5\u30a1\u30fc\u306f\u3001\u79fb\u52d5\u30a6\u30a3\u30f3\u30c9\u30a6\u306e\u539f\u5247\u306b\u5f93\u3063\u3066\u52d5\u4f5c\u3057\u307e\u3059\uff08\u82f1\u8a9e\uff1a \u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6 \uff09\u3001d\u3002 H.\u5727\u7e2e\u3055\u308c\u308b\u30c7\u30fc\u30bf\u30b9\u30c8\u30ea\u30fc\u30e0\u306f\u3001\u53f3\u304b\u3089\u30d0\u30c3\u30d5\u30a1\u30fc\u306b\u62bc\u3057\u8fbc\u307e\u308c\u307e\u3059\u3002\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u8a18\u8f09\u3055\u308c\u3066\u3044\u308b\u3088\u3046\u306b\u3001\u30b7\u30d5\u30c8\u306f\u3001\u8f9e\u66f8\u306e\u5bfe\u5fdc\u3059\u308b\u4e00\u81f4\u306e\u9577\u3055\u3068\u5225\u306e\u4f4d\u7f6e\u306e\u9577\u3055\u3067\u884c\u308f\u308c\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u5197\u9577\u306a\u30c8\u30ea\u30d7\u30eb\u304c\u56de\u907f\u3055\u308c\u308b\u3053\u3068\u3092\u610f\u5473\u3057\u307e\u3059\u3002\u305d\u3046\u3057\u306a\u3044\u3068\u3001\u65b0\u3057\u3044\u6587\u5b57\u306f\u5e38\u306b\u8f9e\u66f8\u3067\u500b\u5225\u306b\u63a1\u7528\u3055\u308c\u307e\u3059\u3002\u4f8b\u3067\u306f\u30013\u756a\u76ee\u306e\u30c8\u30ea\u30d7\u30eb\uff080\u30010\u3001 c \uff09\u305f\u3060\u3057\u3001\u8a18\u9332\u3059\u308b\u306b\u306f\u3001\u5727\u7e2e\u7387\u304c\u5927\u5e45\u306b\u60aa\u5316\u3057\u307e\u3059\u3002\u30de\u30c3\u30c1\u306f\u7dd1\u8272\u3067\u3001\u63cf\u753b\u30c1\u30a7\u30fc\u30f3\u306f\u8d64\u3067\u79fb\u52d5\u3057\u307e\u3059\u3002\u65b0\u3057\u3044\u6587\u5b57\u3092\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u3059\u308b\u5fc5\u8981\u304c\u306a\u3044\u305f\u3081\u306b\u3001\u5951\u7d04\u3067\u767a\u898b\u3055\u308c\u305f\u3088\u308a\u3082\u5e38\u306b\u30b5\u30a4\u30f3\u304c\u79fb\u52d5\u3055\u308c\u308b\u3053\u3068\u306b\u6ce8\u610f\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002 \u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u3092\u4f7f\u7528\u3057\u305fLZ77\u5727\u7e2e\u306e\u4f8b \u30e9\u30a4\u30f3 12\u756a\u76ee 11 \u5341 9 8 7 6 5 4 3 2 \u521d\u3081 0 \u521d\u3081 2 3 4 5 6 7 8 9 \u51fa\u529b \u521d\u3081 \u30d5\u30a1\u30a4\u30eb a a c a a c a b c a \u27f9{displaystyle longrightarrow} \uff080\u30010\u3001 a \uff09\uff09 2 \u30d5\u30a1\u30a4\u30eb a a c a a c a b c a b \u27f9{displaystyle longrightarrow} \uff081\u30011\u3001 c \uff09\uff09 3 \u30d5\u30a1\u30a4\u30eb a a c a a c a b c a b a a \u27f9{displaystyle longrightarrow} \uff083\u30014\u3001 b \uff09\uff09 4 \u30d5\u30a1\u30a4\u30eb a a c a a c a b c a b a a a c \u7d42\u308f\u308a \u27f9{displaystyle longrightarrow} \uff083\u30013\u3001 a \uff09\uff09 5 a a c a a c a b c a b a a a c \u7d42\u308f\u308a  \u27f9{displaystyle longrightarrow} \uff0812\u30013\u3001 \u7d42\u308f\u308a \uff09\uff09 \u5b8c\u4e86  \u6700\u521d\u306b\u898b\u3089\u308c\u305f\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u306f\u4e0d\u660e\u306a\u306e\u3067\u3001\u6700\u521d\u306e\u30ad\u30e3\u30e9\u30af\u30bf\u30fc a \uff080\u30010\u3001 a \uff09\u3002\u3067\u304d\u308b2\u884c\u3067 a \u8f9e\u66f8\uff08\u30de\u30fc\u30af\u30b0\u30ea\u30fc\u30f3\uff09\u304b\u3089\u3059\u3067\u306b\u8aad\u3080\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002 c \u65b0\u3057\u3044\u30b5\u30a4\u30f3\u3068\u3057\u3066\u63a1\u7528\u3055\u308c\u3066\u3044\u307e\u3059\u3002LZ77\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u7279\u6b8a\u306a\u30b1\u30fc\u30b9\u306f\u3001\u4e00\u81f4\u3059\u308b\u6587\u5b57\u5217\u304c\u4e88\u9632\u30a6\u30a3\u30f3\u30c9\u30a6\u306b\u7a81\u304d\u51fa\u3066\u3044\u308b\u305f\u3081\u30013\u884c\u76ee\u3067\u3042\u308b\u305f\u3081\u3001\u3053\u308c\u306f\u7dd1\u306e\u8d64\u306e\u30bb\u30eb\u306e\u8272\u4ed8\u3051\u306b\u3088\u3063\u3066\u793a\u3055\u308c\u3066\u3044\u307e\u3059\u30024\u884c\u76ee\u30685\u884c\u76ee\u306f\u6700\u521d\u306e2\u3064\u306b\u76f8\u5f53\u3057\u307e\u3059\u304c\u3001\u6700\u5f8c\u306e\u30c8\u30ea\u30d7\u30eb1\u3067\u306f\u4f8b\u5916\u304c\u3042\u308a\u307e\u3059\u3002 \u7d42\u308f\u308a  &#8211; \u30c6\u30ad\u30b9\u30c8\u304c\u5b8c\u5168\u306b\u5727\u7e2e\u3055\u308c\u3066\u304a\u308a\u3001\u6b21\u306e\u30b5\u30a4\u30f3\u304c\u306a\u3044\u305f\u3081\u3001\u30de\u30fc\u30af\u306f\u6b21\u306e\u30b5\u30a4\u30f3\u3068\u3057\u3066\u7d39\u4ecb\u3055\u308c\u307e\u3059\u3002 \u5b9f\u884c\u6642\u9593\u5206\u6790 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u6301\u7d9a\u6642\u9593\u306f\u6b21\u306e\u3068\u304a\u308a\u3067\u3059 th \uff08 n \uff09\uff09 {displaystyletheta\uff08n\uff09} \u30c6\u30ad\u30b9\u30c8\u306f\u5727\u7e2e\u4e2d\u306b1\u56de\u306e\u307f\u6e21\u3055\u308c\u308b\u305f\u3081\u3001\u6307\u5b9a\u3055\u308c\u3066\u3044\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u30d7\u30ec\u30d3\u30e5\u30fc\u3068\u8f9e\u66f8\u30d0\u30c3\u30d5\u30a1\u306e\u30b5\u30a4\u30ba\u304c\u4e00\u5b9a\u3067\u3042\u308a\u3001\u5168\u4f1a\u4e00\u81f4\u306e\u30b9\u30c8\u30ea\u30f3\u30b0\u30c1\u30a7\u30fc\u30f3\u306e\u691c\u7d22\u304c\u5927\u304d\u306a\u30c6\u30ad\u30b9\u30c8\u3067\u306f\u91cd\u8981\u3067\u306f\u306a\u3044\u5834\u5408\u306b\u53ef\u80fd\u3067\u3059\u3002\u5b9f\u969b\u306b\u4f7f\u7528\u3059\u308b\u3068\u3001\u901a\u5e38\u306e\u691c\u7d22\uff08\u8ffd\u52a0\u306e\u30c7\u30fc\u30bf\u69cb\u9020\u306a\u3057\uff09\u3092\u4f7f\u7528\u3057\u305f\u5b9f\u88c5\u306f\u304b\u306a\u308a\u9045\u3044\u3067\u3059\u3002 \u9577\u6240\u3068\u77ed\u6240 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] LZ77\u306e\u5927\u304d\u306a\u5229\u70b9\u306f\u3001\u30c6\u30ad\u30b9\u30c8\u306e\u77e5\u8b58\u306a\u3057\u306b\u5727\u7e2e\u3067\u304d\u308b\u3053\u3068\u3067\u3042\u308a\u3001\u7279\u8a31\u3067\u3082\u8a3c\u660e\u3055\u308c\u3066\u3044\u306a\u3044\u3053\u3068\u3067\u3059\u3002 LZ78\uff08LZ77\u306e\u76f4\u63a5\u306e\u5f8c\u7d99\u8005\uff09\u306f\u3001\u30c6\u30ad\u30b9\u30c8\u306e\u518d\u69cb\u6210\u306e\u305f\u3081\u306e\u521d\u671f\u8f9e\u66f8\uff08\u4e3b\u306b\u3059\u3079\u3066\u306e\u30a2\u30a4\u30b3\u30f3\u304c\u4e00\u5ea6\u30bd\u30fc\u30c8\u3055\u308c\u308b\u4e9b\u7d30\u306a\u8f9e\u66f8\uff09\u3092\u5fc5\u8981\u3068\u3057\u30012004\u5e74\u307e\u3067\u7279\u8a31\u306b\u3088\u3063\u3066\u90e8\u5206\u7684\u306b\u4fdd\u8b77\u3055\u308c\u3066\u3044\u307e\u3057\u305f\u3002\u305f\u3060\u3057\u3001LZ77\u306e\u4e3b\u306a\u6b20\u70b9\u306f\u3001\u7279\u306b\u5c0f\u898f\u6a21\u307e\u305f\u306f\u975e\u81ea\u7136\u306a\u8a00\u8a9e\u30c6\u30ad\u30b9\u30c8\u306e\u5834\u5408\u3001\u307e\u305f\u306f\u30c7\u30fc\u30bf\u306e\u91cf\u3092\u62e1\u5927\u3059\u308b\u5834\u5408\u3001\u975e\u5e38\u306b\u5727\u7e2e\u3055\u308c\u308b\u3053\u3068\u3067\u3059\u3002\u3053\u308c\u306f\u3001\u6307\u5b9a\u3055\u308c\u305f\u4f8b\u3067\u660e\u3089\u304b\u306b\u306a\u308a\u307e\u3059\u3002\u5143\u306e\u30c6\u30ad\u30b9\u30c8\u306b\u306f16\u6587\u5b57\u304c\u542b\u307e\u308c\u3066\u304a\u308a\u3001\u5727\u7e2e\u306b\u306f15\u6587\u5b57\u304c\u5fc5\u8981\u3067\u3042\u308b\u305f\u3081\u30011\u3064\u306e\u30b5\u30a4\u30f3\u306e\u7bc0\u7d04\u306e\u307f\u3092\u610f\u5473\u3057\u307e\u3059\u3002 Burrows Wheeler\u306e\u5909\u63db\u3084\u524d\u9762\u3078\u306e\u79fb\u52d5\u30b3\u30fc\u30c9\u3068\u540c\u69d8\u306b\u3001\u4ed6\u306e\u5727\u7e2e\u65b9\u6cd5\u3092\u4f7f\u7528\u3059\u308b\u305f\u3081\u306b\u3001\u305d\u308c\u306f\u524d\u30d7\u30ed\u30bb\u30c3\u30b5\u3068\u3057\u3066\u975e\u5e38\u306b\u9069\u3057\u3066\u3044\u307e\u3059\u3002 B.\u30cf\u30d5\u30de\u30f3\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u304b\u3089\u30c7\u30fc\u30bf\u3092\u52b9\u679c\u7684\u306b\u5727\u7e2e\u3059\u308b\u3002 LZ77\u5727\u7e2e\u30d5\u30a1\u30a4\u30eb\u306e\u6e1b\u5727\u306f\u3001\u4e00\u81f4\u3059\u308b\u30b9\u30c8\u30e9\u30a4\u30ad\u30c1\u30a7\u30fc\u30f3\u306e\u691c\u7d22\u304c\u884c\u308f\u308c\u306a\u3044\u305f\u3081\u3001\u5727\u7e2e\u3088\u308a\u3082\u5927\u5e45\u306b\u7c21\u5358\u3067\u3059\u3002\u3053\u306e\u7528\u8a9e\u306f\u7dda\u5f62\u3067\u3042\u308a\u3001\u5143\u306e\u30c6\u30ad\u30b9\u30c8\u304c\u9577\u3044\u307b\u3069\u591a\u304f\u306e\u30b9\u30c6\u30c3\u30d7\u304c\u3042\u308b\u306e\u3067\u3001 th \uff08 n \uff09\uff09 {displaystyletheta\uff08n\uff09} \u3002 \u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u64ec\u4f3c\u30b3\u30fc\u30c9\u306f\u3001\u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u3092\u4f7f\u7528\u3057\u305fLZ77\u6e1b\u5727\u30b5\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8907\u88fd\u3067\u3059\u3002  \u305f\u3081\u306b  \u6bce\u65e5  \u30c8\u30ea\u30d7\u30eb  \uff08 \u30aa\u30d5\u30bb\u30c3\u30c8 \u3001  \u9577\u3055 \u3001  \u30b7\u30f3\u30dc\u30eb \uff09\uff09  \u3082\u3057\u3082  \u9577\u3055  >  0 ;  \u305d\u308c\u304b\u3089  \u5b9f\u884c  r \u00fc CKW \u00e4 RTS    \u524d  \u51fa\u529b  \u3068  \u30ae\u30d6  \u306b\u9650\u3063\u3066  \u30b5\u30a4\u30f3  out  \u305d\u308c\u307e\u3067  \u4e00  l \u00e4 \u306b  \u304b\u3089  \u9577\u3055  \u5230\u9054\u3057\u305f  \u306f \u3001  \u3067  a  \u00fc \u3078\u305d  \u59cb\u3081\u308b  \u65b0\u3057\u3044  \u3067  \u30aa\u30d5\u30bb\u30c3\u30c8 ;  \u7d42\u308f\u308a  \u3082\u3057\u3082  \u30ae\u30d6  \u30b7\u30f3\u30dc\u30eb  out ;  \u7d42\u308f\u308a  \u305f\u3081\u306b  \u4f8b [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] LZ77\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u306e\u6e1b\u5727\u306b\u306f\u8ffd\u52a0\u306e\u8f9e\u66f8\u306f\u5fc5\u8981\u3042\u308a\u307e\u305b\u3093\u3002\u767a\u884c\u3055\u308c\u305f\u30c8\u30ea\u30d7\u30eb\u306f\u3001\u30c6\u30ad\u30b9\u30c8\u3092\u518d\u69cb\u7bc9\u3059\u308b\u305f\u3081\u306b\u660e\u78ba\u3067\u3059\u3002\u8d64\u3044\u8caf\u8535\u7d30\u80de\u306f\u3001\u6b21\u306e\u7dda\u306e\u518d\u69cb\u7bc9\u306b\u4f7f\u7528\u3055\u308c\u308b\u7d30\u80de\u3067\u3059\u3002 \u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u3092\u4f7f\u7528\u3057\u305fLZ77\u6e1b\u5727\u306e\u4f8b \u30e9\u30a4\u30f3 \u5165\u529b 16 15 14 13 12\u756a\u76ee 11 \u5341 9 8 7 6 5 4 3 2 \u521d\u3081 \u521d\u3081 \u27f9{displaystyle longrightarrow} \uff080\u30010\u3001 a \uff09\uff09 \u30d5\u30a1\u30a4\u30eb a 2 \u27f9{displaystyle longrightarrow} \uff081\u30011\u3001 c \uff09\uff09 \u30d5\u30a1\u30a4\u30eb a a c 3 \u27f9{displaystyle longrightarrow} \uff083\u30014\u3001 b \uff09\uff09 \u30d5\u30a1\u30a4\u30eb a a c a a c a b 4 \u27f9{displaystyle longrightarrow} \uff083\u30013\u3001 a \uff09\uff09 \u30d5\u30a1\u30a4\u30eb a a c a a c a b c a b a 5 \u27f9{displaystyle longrightarrow} \uff0812\u30013\u3001 \u7d42\u308f\u308a \uff09\uff09 a a c a a c a b c a b a a a c \u7d42\u308f\u308a \u5b8c\u4e86  \u30c8\u30ea\u30d7\u30eb\u306e\u6700\u521d\u306e\u30a8\u30f3\u30c8\u30ea\u304c\u540c\u30580\u306e\u5834\u5408\u3001\u30c8\u30ea\u30d7\u30eb\u306e\u6700\u5f8c\u306e\u30a8\u30f3\u30c8\u30ea\u304c\u30c6\u30ad\u30b9\u30c8\u306b\u6dfb\u4ed8\u3055\u308c\u307e\u3059\uff081\u884c\u76ee\u3092\u53c2\u7167\uff09\u3002\u5165\u529b\u3092\u4f7f\u7528\u3057\u305f2\u884c\u76ee\uff081\u30011\u3001 c \uff09\u30011\u884c\u76ee\u304b\u3089\u518d\u69cb\u7bc9\u3055\u308c\u305f\u30c6\u30ad\u30b9\u30c8\u306e\u6700\u521d\u306e\u30a8\u30f3\u30c8\u30ea\uff08\u4f4d\u7f6e1\u306e\u30c8\u30ea\u30d7\u30eb\u306e\u6700\u521d\u306e\u30a8\u30f3\u30c8\u30ea\u3068\u9577\u30551\u306e\u30c8\u30ea\u30d7\u30eb\u306e2\u756a\u76ee\u306e\u30a8\u30f3\u30c8\u30ea\uff09\u4f7f\u7528\u3057\u3066\u304b\u3089\u30b5\u30a4\u30f3 c \u5f8c\u308d\u306b\u6dfb\u4ed8\u3055\u308c\u3066\u3044\u307e\u3059\u30023\u884c\u76ee\u3067\u306f\u3001\u518d\u4f7f\u7528\u3055\u308c\u305f\u6587\u5b57\u30c1\u30a7\u30fc\u30f3\u306e\u9577\u3055\u306f\u8f9e\u66f8\u306e\u4fdd\u5b58\u3055\u308c\u305f\u30c7\u30fc\u30bf\u3088\u308a\u3082\u9577\u304f\uff08\u9577\u30554\u3067\u3059\u304c\u3001\u30b9\u30c8\u30ec\u30fc\u30b8\u30bb\u30eb3\u304b\u30893\u3064\u306e\u30bb\u30eb\u306e\u307f\u304c\u5229\u7528\u53ef\u80fd\u3067\u3059\uff09\u3002 a \u51fa\u529b\u3002\u305d\u3046\u306a\u308a\u307e\u3059 b \u51e6\u7406\u3059\u308b\u30c8\u30ea\u30d7\u30eb\u306e\u6700\u5f8c\u306e\u30a8\u30f3\u30c8\u30ea\u3068\u3057\u3066\u30024\u884c\u76ee\u30685\u884c\u76ee\u306f\u540c\u69d8\u306b\u7406\u89e3\u3055\u308c\u308b\u3079\u304d\u3067\u3059\u3002\u30a8\u30f3\u30c9\u30b5\u30a4\u30f3\u306f\u3001\u30c6\u30ad\u30b9\u30c8\u306e\u7d42\u308f\u308a\u3068\u3057\u3066\u30b0\u30ed\u30fc\u30d0\u30eb\u306b\u7406\u89e3\u3055\u308c\u308b\u305f\u3081\u3001\u518d\u69cb\u7bc9\u3067\u306f\u7121\u8996\u3055\u308c\u307e\u3059\u3002\u5b8c\u5168\u306b\u518d\u69cb\u7bc9\u3055\u308c\u305f\u30c6\u30ad\u30b9\u30c8\u306f\u3067\u3059 AACTA\u306e\u4e71\u7528 \u3002 \u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306eLZ77-factorization\u306e\u3088\u308a\u30e9\u30f3\u30bf\u30a4\u30e0\u52b9\u7387\u306e\u8a08\u7b97\u306e\u305f\u3081\u306b\u3001\u5b8c\u5168\u306a\u6587\u5b57\u5217\u306e\u56e0\u6570\u5206\u89e3\u3092\u4ee5\u4e0b\u3067\u8a08\u7b97\u3057\u3001\u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u306e\u539f\u7406\u3092\u653e\u68c4\u3057\u307e\u3059\u3002\u6700\u5f8c\u306b\u3001\u6587\u5b57\u5217\u5168\u4f53\u306eLZ77\u5727\u7e2e\u3082\u3044\u304f\u3064\u304b\u306e\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u3067\u4f7f\u7528\u3055\u308c\u307e\u3059\uff08\u30bb\u30af\u30b7\u30e7\u30f3\u3092\u53c2\u7167\uff09\u3002 \u8ffd\u52a0\u306e\u30c7\u30fc\u30bf\u69cb\u9020\u306e\u52a9\u3051\u3092\u501f\u308a\u3066\u3001\u7528\u8a9e\u306b\u95a2\u3057\u3066\u306f\u3001\u6587\u5b57\u30c1\u30a7\u30fc\u30f3\u306eLZ77\u56e0\u6570\u5206\u89e3\u306e\u52b9\u7387\u7684\u306a\u8a08\u7b97\u304c\u53ef\u80fd\u3067\u3059\u3002\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306e\u5834\u5408 \u30d0\u30c4 {displaystyle x} \u6307\u5b9a s a {displaystyleSa} \u63a5\u5c3e\u8f9e\u30a2\u30ec\u30a4\u3068 \u79c1 s a {displaystyle isa} \u9006\u306e\u63a5\u5c3e\u8f9e\u8eca\u304b\u3089 \u30d0\u30c4 {displaystyle x} \u3001d\u3002 H.\u305d\u3046\u3067\u3059 \u79c1 s a [ \u79c1 ] = j {displaystyle isa [i] = j} \u6b63\u78ba\u306b\u3044\u3064 s a [ j ] = \u79c1 {displaystyle sa [j] = i} \u3002\u307e\u305f\u3001\u8aac\u660e\u3057\u3066\u304f\u3060\u3055\u3044 l c p \uff08 \u79c1 \u3001 j \uff09\uff09 {displaystyle lcp\uff08i\u3001j\uff09} \u6587\u5b57\u5217\u30c1\u30a7\u30fc\u30f3\u306e\u6700\u3082\u9577\u3044\u4e00\u822c\u7684\u306a\u63a5\u982d\u8f9e\u306e\u9577\u3055 \u30d0\u30c4 [ s a [ \u79c1 ] \u3002 \u3002 n ] {displaystyle x [sa [i] .. n]} \u3068 \u30d0\u30c4 [ s a [ j ] \u3002 \u3002 n ] {displaystyle x [sa [j] .. n]} \u3001\u305d\u308c\u306b\u3088\u3063\u3066 n = | \u30d0\u30c4 | {displaystyle n = | x |} \u306f\u3002 \u8a08\u7b97\u3067\u306f\u3001\u8981\u56e0\u306b\u5bfe\u3057\u3066\u305d\u308c\u3092\u4f7f\u7528\u3057\u307e\u3059 \u306e j {displaystyle w_ {j}} \u304b\u3089 \u30d0\u30c4 {displaystyle x} \u3068 1&#8243;>\u4f4d\u7f6e\u3092\u6c7a\u5b9a\u3059\u308b\u305f\u3081 p o s {displaystyle pos} Tupel\u306e\u307f\u306e\u30c6\u30ad\u30b9\u30c8\u4f4d\u7f6e\u306e\u307f s a [ n s \u306e [ \u79c1 s a [ j ] ] ] {displaystyle sa [nsv [isa [j]]]} \u3068 s a [ p s \u306e [ \u79c1 s a [ j ] ] ] {displaystyle sa [psv [isa [j]]}} \u8003\u616e\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u3042\u308b n s \u306e [ j ] = m \u79c1 n { \u79c1 \u2208 { j + \u521d\u3081 \u3001 &#8230; \u3001 n } | s a [ \u79c1 ] < s a [ j ] } {displaystyle nsv [j] = min {iin {j+1\u3001ldots\u3001n}\u3001|\u3001sa [i] \uff08NSV\u306f\u7565\u3067\u3059 \u6b21\u306e\u5c0f\u3055\u306a\u5024 \uff09 \u3068 p s \u306e [ j ] = m a \u30d0\u30c4 { \u79c1 \u2208 { \u521d\u3081 \u3001 &#8230; \u3001 j  &#8211;  \u521d\u3081 } | s a [ \u79c1 ] < s a [ j ] } {displaystyle psv [j] = max {iin {1\u3001ldots\u3001j-1}\u3001|\u3001sa [i] \uff08PSV\u306f\u7565\u3067\u3059 \u4ee5\u524d\u306e\u5c0f\u3055\u306a\u5024 \uff09\u3002 [3] \u64ec\u4f3c\u30b3\u30fc\u30c9 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 lz_factor\uff08i\u3001psv\u3001nsv\uff09 \u30ea\u30bf\u30fc\u30f3\u3068\u3057\u3066\u3001\u6b21\u306e\u8981\u56e0\u306e\u958b\u59cb\u4f4d\u7f6e\u304c\u914d\u4fe1\u3055\u308c\u307e\u3059  \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0  LZ_Factor \uff08 \u79c1 \u3001  PSV \u3001  \u30bd\u9023 \uff09\uff09 \uff1a  \u3082\u3057\u3082  LCP \uff08 \u79c1 \u3001  PSV \uff09\uff09  >  LCP \uff08 \u79c1 \u3001  \u30bd\u9023 \uff09\uff09 ;  \u305d\u308c\u304b\u3089  \uff08 Pos \u3001  \u305d\u308c\u3060\u3051 \uff09\uff09  < -   \uff08 PSV \u3001  LCP \uff08 \u79c1 \u3001  PSV \uff09\uff09\uff09  \u305d\u308c\u4ee5\u5916  \uff08 Pos \u3001  \u305d\u308c\u3060\u3051 \uff09\uff09  < -   \uff08 \u30bd\u9023 \u3001  LCP \uff08 \u79c1 \u3001  \u30bd\u9023 \uff09\uff09\uff09  \u7d42\u308f\u308a  \u3082\u3057\u3082  \u3082\u3057\u3082  \u305d\u308c\u3060\u3051  =  0 ;  \u305d\u308c\u304b\u3089  Pos  < -   \u79c1  \u7d42\u308f\u308a  \u3082\u3057\u3082  \u3082\u3057\u3082  \u79c1  +  \u305d\u308c\u3060\u3051  >  n ;  \u305d\u308c\u304b\u3089  \u5370\u5237  \u8981\u7d20 \uff08 Pos \u3001  \u305d\u308c\u3060\u3051 \u3001  '\u7d42\u308f\u308a' \uff09\uff09  \u305d\u308c\u4ee5\u5916  \u5370\u5237  \u8981\u7d20 \uff08 Pos \u3001  \u305d\u308c\u3060\u3051 \u3001  \u30d0\u30c4 [ \u79c1 + \u305d\u308c\u3060\u3051 ]\uff09\uff09  \u7d42\u308f\u308a  \u3082\u3057\u3082  \u623b\u308b  \u79c1  +  \u30de\u30c3\u30af\u30b9 \uff08 \u305d\u308c\u3060\u3051 \u3001  \u521d\u3081 \uff09\uff09  2\u3064\u306e\u914d\u5217 n s \u306e {displaystyle nsv} \u3068 p s \u306e {displaystyle psv} \u63a5\u5c3e\u8f9e\u30de\u30fc\u30b8\u30f3\u304b\u3089\u7f36 s a {displaystyleSa} \u7dda\u5f62\u6642\u9593\u306b\u8a08\u7b97\uff1a  \u305f\u3081\u306b  \u79c1  < -   2  \u306b  n + \u521d\u3081 ;  \u3059\u308b  j  < -   \u79c1  -  \u521d\u3081  \u305d\u306e\u9593  \u5b9a\u7fa9\u3055\u308c\u3066\u3044\u307e\u3059 \uff08 j \uff09\uff09  \u3068  \u306e\u4e0a [ \u79c1 ]  <  \u306e\u4e0a [ j ] ;  \u3059\u308b  \u30bd\u9023 [ j ]  < -   \u79c1  j  < -   PSV [ j ]  \u7d42\u308f\u308a  \u305d\u306e\u9593  PSV [ \u79c1 ]  < -   j  \u7d42\u308f\u308a  \u305f\u3081\u306b  \u6700\u5f8c\u306b\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u7d9a\u304d\u3001\u30ad\u30e3\u30e9\u30af\u30bf\u30fc\u30c1\u30a7\u30fc\u30f3\u306eLZ77\u56e0\u6570\u5206\u89e3\u3092\u8a08\u7b97\u3057\u307e\u3059 \u30d0\u30c4 {displaystyle x}   \u8a08\u7b97\u3057\u307e\u3059  \u306e\u4e0a \u3001  \u4e00 \u3001  \u30bd\u9023  \u3068  PSV  f \u00fc r  \u30d0\u30c4  k  < -   \u521d\u3081  \u305d\u306e\u9593  k  { l | \u30d0\u30c4 [ \u79c1 &#8230; \u79c1 + l  &#8211;  \u521d\u3081 ] \u306e\u8981\u56e0\u3067\u3059 \u30d0\u30c4 [ \u521d\u3081 &#8230; \u79c1 + l  &#8211;  2 ] } \uff09\uff09 {displaystyle lpf [i] = max\uff08{0} cup {l\u3001|\u3001x [idots i+l-1] {text {ist ein fake fake von}} x [1dots i+l-2]}}}} \u3002 LPF\u30a2\u30ec\u30a4\u306f\u3001\u7dda\u5f62\u6642\u9593\u306b\u6587\u5b57\u30c1\u30a7\u30fc\u30f3\u306eLZ77\u56e0\u6570\u5206\u89e3\u304b\u3089\u8a08\u7b97\u3067\u304d\u307e\u3059\u3002LPF\u30a2\u30ec\u30a4\u306f\u3001\u3068\u308a\u308f\u3051\u3001\u4e0a\u8a18\u306eNSV\u304a\u3088\u3073PSV\u30a2\u30ec\u30a4\u3092\u4f7f\u7528\u3057\u3066\u8a08\u7b97\u3067\u304d\u307e\u3059\u3002 [3] l p f [ \u79c1 ] = m a \u30d0\u30c4 \uff08 l c p \uff08 \u79c1 \u3001 s a [ n s \u306e [ \u79c1 s a [ \u79c1 ] ] ] \uff09\uff09 \u3001 l c p \uff08 \u79c1 \u3001 s a [ p s \u306e [ \u79c1 s a [ \u79c1 ] ] ] \uff09\uff09 \uff09\uff09 {displaystyle lpf [i] = max\uff08lcp\uff08i\u3001sa [nsv [i]]\uff09\u3001lcp\uff08i\u3001sa [psv [i]]\uff09}\uff09}\uff09}  \u30c6\u30fc\u30d6\u30eb\u306b\u30ea\u30b9\u30c8\u3055\u308c\u3066\u3044\u308b\u3044\u304f\u3064\u304b\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5b9f\u88c5\u306e\u305f\u3081\u306b s {displaystyleS} \u8ffd\u52a0\u306e\u30e1\u30e2\u30ea\u304c\u5fc5\u8981\u3067\u3059\u3002\u30c6\u30fc\u30d6\u30eb\u3067\u306f\u3001\u30b9\u30bf\u30c3\u30af\u306e\u4f7f\u7528\u304c\u30e1\u30e2\u30ea\u8981\u4ef6\u306b\u53d6\u308a\u4ed8\u3051\u3089\u308c\u3066\u3044\u307e\u3059 + {displaystyle +} \u8868\u793a\u3055\u308c\u3066\u3044\u307e\u3059\u3002\u30b9\u30bf\u30c3\u30af\u30e1\u30e2\u30ea\u306e\u30b5\u30a4\u30ba\u306f\u5236\u9650\u3055\u308c\u307e\u3059 | s | = n {displaystyle | s | = n}  &#8211; \u3053\u308c\u306f\u3001\u6587\u5b57\u5217\u304c\u5f62\u72b6\u3092\u30c1\u30a7\u30fc\u30f3\u3059\u308b\u5834\u5408\u306b\u5f53\u3066\u306f\u307e\u308a\u307e\u3059 \u30d0\u30c4 = a n {displaystyle x = alpha ^{n}} \u3068 a \u2208 a {sigma\u306edisplaystyle alpha} \u6301\u3063\u3066\u3044\u308b\u3002\u671f\u5f85\u3055\u308c\u3066\u3044\u307e\u3059 | s | \u2208 o \uff08 \u30ed\u30b0 |a |\u2061 n \uff09\uff09 {displaystyle | s | in o\uff08log _ {| sigma |} n\uff09} \u3002 [2] \u4eca\u65e5\u3001LZ77\u5727\u7e2e\u3068a\u3002 Game Boy Advance\u3001AutoCAD DWG\u5f62\u5f0f\u3001\u305d\u306e\u4ed6\u306e\u7d44\u307f\u8fbc\u307f\u30b7\u30b9\u30c6\u30e0\u3067\u307e\u3060\u4f7f\u7528\u3055\u308c\u3066\u3044\u307e\u3059\u3002 Huffman Coding\u3068\u7d44\u307f\u5408\u308f\u305b\u3066\u3001LZ77\u306f\u975e\u5e38\u306b\u3088\u304f\u77e5\u3089\u308c\u305f\u5727\u7e2e\u30d7\u30ed\u30b0\u30e9\u30e0\u3068\u30b0\u30e9\u30d5\u30a3\u30c3\u30af\u5f62\u5f0fPNG\u3067\u4f7f\u7528\u3055\u308c\u308b\u3001\u975e\u5e38\u306b\u4f7f\u7528\u3055\u308c\u3066\u3044\u308bDERGLATE\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u4f7f\u7528\u3055\u308c\u307e\u3059\u3002 LZ77\u304c\u7279\u8a31\u3067\u8a3c\u660e\u3055\u308c\u3066\u3044\u306a\u3044\u3068\u3044\u3046\u4e8b\u5b9f\u306f\u30011\u5e74\u5f8c\u306b\u516c\u958b\u3055\u308c\u305f\u5f8c\u7d99LZ78\u3088\u308a\u3082\u30d7\u30ed\u30bb\u30b9\u304c\u307e\u3060\u597d\u307e\u308c\u3066\u3044\u308b\u7406\u7531\u3067\u3042\u308b\u306f\u305a\u3067\u3059\u3002 \u6587\u5b57\u9396\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u51e6\u7406\u3067\u306f\u3001LZ77-factorization\u304c\u6587\u5b57\u5217\u306e\u898f\u5247\u6027\u306e\u8a08\u7b97\u306b\u4f7f\u7528\u3055\u308c\u307e\u3059\u3002\u56e0\u6570\u5206\u89e3\u306f\u3001\u30b9\u30e9\u30a4\u30c9\u30a6\u30a3\u30f3\u30c9\u30a6\u5185\u3060\u3051\u3067\u306a\u304f\u3001\u6587\u5b57\u5217\u5168\u4f53\u3067\u5e38\u306b\u8003\u616e\u3055\u308c\u307e\u3059\u3002\u3055\u3089\u306b\u3001\u5143\u306e\u6587\u5b57\u5217\u304c\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u3067\u4f7f\u7528\u53ef\u80fd\u3067\u3042\u308a\u3001\u518d\u69cb\u7bc9\u3059\u308b\u5fc5\u8981\u304c\u306a\u3044\u305f\u3081\u3001\u51fa\u529b\u3092\u7c21\u7d20\u5316\u3067\u304d\u307e\u3059\u3002 LZ77\u56e0\u6570\u5206\u89e3\u3092\u4f7f\u7528\u3067\u304d\u308b\u554f\u984c\u306e\u9078\u629e\u306f\u3001\u6b21\u306e\u30ea\u30b9\u30c8\u306b\u8a18\u8f09\u3055\u308c\u3066\u3044\u307e\u3059\u3002 \u5727\u7e2e\u54c1\u8cea\u306f\u3001\u8f9e\u66f8\u306e\u30b5\u30a4\u30ba\u306b\u76f4\u63a5\u4f9d\u5b58\u3057\u307e\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u826f\u597d\u306a\u5727\u7e2e\u901f\u5ea6\u3092\u53d6\u5f97\u3059\u308b\u305f\u3081\u306b\u306f\u3001\u30b9\u30e9\u30a4\u30c7\u30a3\u30f3\u30b0\u30a6\u30a3\u30f3\u30c9\u30a6\u306f\u4e00\u5b9a\u306e\u6700\u5c0f\u30b5\u30a4\u30ba\u3092\u9054\u6210\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u5727\u7e2e\u3055\u308c\u308b\u30c6\u30ad\u30b9\u30c8\u306f\u3001\u30ec\u30ad\u30b7\u30b3\u30f3\u306e\u5404\u30a8\u30f3\u30c8\u30ea\uff08\u30bb\u30af\u30b7\u30e7\u30f3\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u53c2\u7167\uff09\u3068\u6bd4\u8f03\u3059\u308b\u5fc5\u8981\u304c\u3042\u308b\u305f\u3081\u3001\u5727\u7e2e\u306b\u5fc5\u8981\u306a\u6642\u9593\u306f\u3001\u30a6\u30a3\u30f3\u30c9\u30a6\u306e\u30b5\u30a4\u30ba\u304c\u76f4\u7dda\u7684\u306b\u5897\u52a0\u3057\u307e\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u7d14\u7c8b\u306a\u5f62\u306eLZ77\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u6700\u521d\u306f\u307b\u3068\u3093\u3069\u6ce8\u76ee\u3055\u308c\u307e\u305b\u3093\u3067\u3057\u305f\u3002 James Storer\u3068Thomas Szymanski\u306f\u30011982\u5e74\u306b\u73fe\u5728Lempel-Ziv-Storer-Szymanski\uff08LZSS\uff09\u3068\u547c\u3070\u308c\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3044\u304f\u3064\u304b\u306e\u554f\u984c\u3092\u6539\u5584\u3057\u307e\u3057\u305f\u3002\u30ec\u30ad\u30b7\u30b3\u30f3\u306e\u3059\u3079\u3066\u306e\u30a8\u30f3\u30c8\u30ea\u3068\u5727\u7e2e\u3055\u308c\u308b\u30c6\u30ad\u30b9\u30c8\u306e\u6bd4\u8f03\u306f\u3001\u52b9\u7387\u7684\u306a\u69cb\u7bc9\u306e\u305f\u3081\u306e\u30bb\u30af\u30b7\u30e7\u30f3\u306e\u3088\u3046\u306b\u52b9\u7387\u7684\u306a\u5b9f\u88c5\u306b\u306f\u9069\u7528\u3055\u308c\u307e\u305b\u3093\u3002 \u30aa\u30d5\u30bb\u30c3\u30c8\u30ec\u30f3\u30da\u30ebZIV\u306e\u6e1b\u5c11\uff08\u30ed\u30eb\u30c4\u3082 Lempel Ziv Ross Williams \u3001\u30ed\u30b9\u30fb\u30a6\u30a3\u30ea\u30a2\u30e0\u30ba\u30011991\u5e74\uff09\u304a\u3088\u3073Lempel-Ziv-Markow-Algorithm\uff08LZMA\u3001Igor Pavlov\u30011998\uff09\u3001\u5f7c\u306f\u3088\u308a\u6709\u540d\u3067\u73fe\u4ee3\u306e\u5f8c\u7d99\u8005\u3092\u898b\u3064\u3051\u307e\u3057\u305f\u3002 \u95a2\u9023\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u30de\u30fc\u30af\u30fb\u30cd\u30eb\u30bd\u30f3\u3001\u30b8\u30e3\u30f3\u30fb\u30eb\u30fc\u30d7\u30fb\u30ac\u30a4\u30ea\u30fc\uff1a \u30c7\u30fc\u30bf\u5727\u7e2e\u672c \u3002\u7b2c2\u7248\u200b\u200b\u3002 M\uff06T Books\u3001\u30cb\u30e5\u30fc\u30e8\u30fc\u30af1996\u3001ISBN 1-55851-434-1 Anisa Al-Hafeedh et al\u3002\uff1a \u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u30d9\u30fc\u30b9\u306eLEMPEL-ZIV LZ77\u56e0\u6570\u5206\u89e3\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u6bd4\u8f03 \u3002\u306e\uff1a ACM\u30b3\u30f3\u30d4\u30e5\u30fc\u30c6\u30a3\u30f3\u30b0\u8abf\u67fb \u3001nr\u3002 1\u3001\u7b2c45\u5dfb\u30012012\u5e74\u3001S\u30025\uff1a1\u20135\uff1a17 AnnetteLe\u00dfm\u00f6llmann\uff1a \u30b8\u30c3\u30d1\u30fc\u306e\u5341\u5b57\u7dda\u3067 &#8211; \u5727\u7e2e\u30d7\u30ed\u30b0\u30e9\u30e0\u306f\u3001\u5358\u8a9e\u3092\u7406\u89e3\u3057\u3066\u3044\u306a\u304f\u3066\u3082\u3001\u30c6\u30ad\u30b9\u30c8\u306e\u8457\u8005\u3092\u8033\u306b\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059 \u3002 \u306e\uff1a \u6642\u9593 \u3001 \u3044\u3044\u3048\u3002 12\/2002\u3001p\u300245 \u2191  \u30b8\u30a7\u30a4\u30b3\u30d6\u30fb\u30b8\u30d6\u3001\u30a2\u30d6\u30e9\u30cf\u30e0\u30fb\u30ec\u30f3\u30da\u30eb\uff1a \u30b7\u30fc\u30b1\u30f3\u30b7\u30e3\u30eb\u30c7\u30fc\u30bf\u5727\u7e2e\u306e\u305f\u3081\u306e\u30e6\u30cb\u30d0\u30fc\u30b5\u30eb\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u3002\u306e\uff1a \u60c5\u5831\u7406\u8ad6\u306b\u95a2\u3059\u308bIEEE\u30c8\u30e9\u30f3\u30b6\u30af\u30b7\u30e7\u30f3\u3001 nr\u3002 3\u3001\u7b2c23\u5dfb\u30011977\u5e74\u3001S\u3002337\u2013343 Cs.duke.edu \uff08PDF; 481 kb\uff09  \u2191 a b c d  Anisa Al-Hafeedh et al\u3002\uff1a \u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u30d9\u30fc\u30b9\u306eLEMPEL-ZIV LZ77\u56e0\u6570\u5206\u89e3\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u6bd4\u8f03 \u3002\u306e\uff1a ACM\u30b3\u30f3\u30d4\u30e5\u30fc\u30c6\u30a3\u30f3\u30b0\u8abf\u67fb \u3001nr\u3002 1\u3001\u7b2c45\u5dfb\u30012012\u5e74\u3001S\u30025\uff1a1\u20135\uff1a17  \u2191 a b c  JuhaK\u00e4rkk\u00e4inen\u3001Dominik Kempa\u3001Simon J. Puglisi\uff1a \u7dda\u5f62\u6642\u9593lempel-ziv\u56e0\u6570\u5206\u89e3\uff1a\u30b7\u30f3\u30d7\u30eb\u3001\u9ad8\u901f\u3001\u5c0f\u3055\u3044 \u3002\u306e\uff1a CPM 2013 \u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30b5\u30a4\u30a8\u30f3\u30b9\u306e\u8b1b\u7fa9\u30ce\u30fc\u30c8\u3001\u30dc\u30ea\u30e5\u30fc\u30e07922\u3001Springer\u30012013\u3001ISBN 978-3-642-38904-7  \u2191  Mohamed I. Abouelhoda\u3001Stefan Kurtz\u3001Enno Ohlebuke\uff1a \u63a5\u5c3e\u8f9e\u30c4\u30ea\u30fc\u3092\u5f37\u5316\u3055\u308c\u305f\u30b5\u30d5\u30a3\u30c3\u30af\u30b9\u914d\u5217\u306b\u7f6e\u304d\u63db\u3048\u307e\u3059 \u3002\u306e\uff1a Journal of Displete\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u3001nr\u3002 1\u3001\u7b2c2\u5dfb\u30012004\u5e74\u3001S\u300253\u201386  \u2191 a b c  \u30ae\u30e3\u30f3\u30b0\u30c1\u30a7\u30f3\u3001\u30b5\u30a4\u30e2\u30f3J.\u30d7\u30fc\u30ea\u30b7\u3001\u30a6\u30a3\u30ea\u30a2\u30e0F.\u30b9\u30df\u30b9\uff1a \u6587\u5b57\u5217\u5185\u306e\u3059\u3079\u3066\u306e\u5b9f\u884c\u3092\u8a08\u7b97\u3059\u308b\u305f\u3081\u306e\u9ad8\u901f\u304b\u3064\u5b9f\u7528\u7684\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u3002\u306e\uff1a \u30b3\u30f3\u30d3\u30ca\u30c8\u30ea\u30a2\u30eb\u30d1\u30bf\u30fc\u30f3\u30de\u30c3\u30c1\u30f3\u30b0\u3001\u7b2c18\u56de\u5e74\u6b21\u30b7\u30f3\u30dd\u30b8\u30a6\u30e0\u3001CPM 2007\u3001\u30ed\u30f3\u30c9\u30f3\u3001\u30ab\u30ca\u30c0\u30012007\u5e747\u67089\u301c11\u65e5\u3001\u8b70\u4e8b\u9332 \u3001S\u3002307\u2013315  \u2191 a b c  \u30ae\u30e3\u30f3\u30b0\u30c1\u30a7\u30f3\u3001\u30b5\u30a4\u30e2\u30f3J.\u30d7\u30fc\u30ea\u30b7\u3001\u30a6\u30a3\u30ea\u30a2\u30e0F.\u30b9\u30df\u30b9\uff1a \u3088\u308a\u5c11\u306a\u3044\u6642\u9593\u3068\u7a7a\u9593\u3092\u4f7f\u7528\u3057\u305fLempel-ZIV\u56e0\u6570\u5206\u89e3 \u3002\u306e\uff1a \u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30b5\u30a4\u30a8\u30f3\u30b9\u306e\u6570\u5b66 \u3001nr\u3002 4\u3001\u7b2c1\u5dfb\u30012008\u5e74\u3001S\u3002605\u2013623  \u2191 a b  Maxime Crochemore\u3001Lucian Ilie\uff1a \u7dda\u5f62\u6642\u9593\u3068\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u3067\u6700\u3082\u9577\u3044\u4ee5\u524d\u306e\u8981\u56e0\u3092\u8a08\u7b97\u3057\u307e\u3059 \u3002\u306e\uff1a \u60c5\u5831\u51e6\u7406\u30ec\u30bf\u30fc \u3001nr\u3002 2\u3001Volume 106\u30012008\u3001S\u300275\u201380  \u2191  Maxime Crochemore\uff1a \u30c8\u30e9\u30f3\u30b9\u30c7\u30e5\u30fc\u30b5\u30fc\u3068\u88dc\u511f \u3002\u306e\uff1a \u7406\u8ad6\u7684\u306a\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30b5\u30a4\u30a8\u30f3\u30b9 \u3001nr\u3002 1\u3001\u7b2c45\u5dfb\u30011986\u3001S\u300263\u201386  \u2191  Jens Stoye\u3001Dan Gusfield\uff1a \u63a5\u5c3e\u8f9e\u30c4\u30ea\u30fc\u3092\u4f7f\u7528\u3057\u305f\u9023\u7d9a\u3057\u305f\u7e70\u308a\u8fd4\u3057\u306e\u30b7\u30f3\u30d7\u30eb\u3067\u67d4\u8edf\u306a\u691c\u51fa \u3002\u306e\uff1a \u7406\u8ad6\u7684\u306a\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30b5\u30a4\u30a8\u30f3\u30b9 \u3001nr\u3002 1\u20132\u3001\u7b2c270\u5dfb\u30012002\u5e74\u3001S\u3002843\u2013856  \u2191  \u30ed\u30fc\u30de\u30f3\u30fbM\u30fb\u30b3\u30eb\u30d1\u30b3\u30d5\u3001\u30b0\u30ec\u30b4\u30ea\u30fc\u30fb\u30af\u30c1\u30a7\u30ed\u30d5\uff1a \u56fa\u5b9a\u30ae\u30e3\u30c3\u30d7\u306e\u3042\u308b\u7e70\u308a\u8fd4\u3057\u3092\u898b\u3064\u3051\u308b \u3002\u306e\uff1a \u6587\u5b57\u5217\u51e6\u7406\u3068\u60c5\u5831\u691c\u7d22\u306b\u95a2\u3059\u308b\u7b2c7\u56de\u56fd\u969b\u30b7\u30f3\u30dd\u30b8\u30a6\u30e0\u306e\u8b70\u4e8b\u9332\uff08Spire\uff09 \u30012000\u3001IEEE Computer Society\u3001S\u3002162\u2013168  \u2191  \u30de\u30a4\u30b1\u30ebG.\u30e1\u30a4\u30f3\uff1a \u5de6\u7aef\u306e\u6700\u5927\u5468\u671f\u3092\u691c\u51fa\u3057\u307e\u3059 \u3002\u306e\uff1a \u500b\u5225\u306e\u9069\u7528\u6570\u5b66 \u3001nr\u3002 1\u20132\u3001\u7b2c25\u5dfb\u30011989\u5e74\u3001S\u3002145\u2013153       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/6038#breadcrumbitem","name":"LZ77  &#8211; \u30a6\u30a3\u30ad\u30da\u30c7\u30a3\u30a2"}}]}]