compresser/décompresser une map

 

ulis, 2006-01-30. Les procédures pour compresser/décompresser une map.

2006-02-02, v2 : le compte de caractères a été codé avec des caractères sur 256 (au lieu de chiffres sur 16).


Pourquoi

Pour faire maigrir les grosses maps. A n'utiliser qu'en cas de nécessité.


Comment

Compression au moyen du RLE : run length encoding. Si on trouve une séquence du même caractère, on remplace la séquence par le nombre de caractère suivi du caractère. La séquence est encodée par *xcx est un nombre hexadécimal représentant le compte de caractères dans la séquence et c est le caractère à répéter.


Utilisation

  compress map
  # map : la map à compresser

  uncompress map
  # map : la map à décompresser

La procédure de compression

  # compress a map

  proc compress {map} \
  {
    # v2
    # check if already compressed
    if {[string first * $map] > -1} { return $map }
    # compress (RLE encoding)
    set map2 [list [lindex $map 0]]
    set max [string length [lindex $map 1]]
    foreach line [lrange $map 1 end] \
    {
      set line2 ""
      set last [string index $line 0]
      set count 1
      for {set i 1} {$i < $max} {incr i} \
      {
        # get current
        set cur [string index $line $i]
        # check if out of run
        if {$cur == $last && $count < 255} { incr count } \
        else \
        {
          # out of run: encode
          if {$count == 1} \
          { append line2 $last } \
          elseif {$count < 3} \
          { append line2 [string repeat $last $count] } \
          else \
          { append line2 "*[format %c $count]$last" }
          # prepare next run
          set last $cur
          set count 1
        }
      }
      # encode remaining chars
      if {$count == 1} \
      { append line2 $last } \
      elseif {$count < 4} \
      { append line2 [string repeat $last $count] } \
      else \
      { append line2 "*[format %c $count]$last" }
      lappend map2 $line2
    }
    # return compressed map
    return $map2
  }

La procédure de décompression

  # uncompress a map

  proc uncompress {map} \
  {
    # v2
    # check if compressed
    if {[string first * $map] == -1} { return $map }
    # uncompress (RLE decoding)
    set map2 [lrange $map 0 0]
    foreach line [lrange $map 1 end] \
    {
      set line2 ""
      set i 0
      set max [string length $line]
      while {$i < $max} \
      {
        set char [string index $line $i]
        # check current char
        if {$char == "*"} \
        {
          # expand encoded run
          incr i
          set char [string index $line $i]
          scan $char %c count
          incr i
          set char [string index $line $i]
          append line2 [string repeat $char $count]
        } \
        else \
        { append line2 $char }
        # next char
        incr i
      }
      lappend map2 $line2
    }
    # return uncompressed map
    return $map2
  }

Démo

    set map \
    {
      0
      0000aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa0000
      00aaddddddddddddddddddddddddddddddddddddddddddaa00
      0adddddddddddddddddddddddddddddddddddddddddddddda0
      0adddddddddddddddddddddddddddddddddddddddddddddda0
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      adddddddddddddddddddddddddddddddddddddddddddddddda
      9cccccccccccccccccccccccccccccccccccccccccccccccc9
      9cccccccccccccccccccccccccccccccccccccccccccccccc9
      9cccccccccccccccccccccccccccccccccccccccccccccccc9
      9cccccccccccccccccccccccccccccccccccccccccccccccc9
      9cccccccccccccccccccccccccccccccccccccccccccccccc9
      09cccccccccccccccccccccccccccccccccccccccccccccc90
      09cccccccccccccccccccccccccccccccccccccccccccccc90
      0099dddddddddddddddddddddddddddddddddddddddddd9900
      00009999999999999999999999999999999999999999990000
    }
    map2file $map uncompressed.map
    set compress 1
    map2file $map compressed.map $compress
    foreach file {uncompressed compressed} \
    {
      puts "$file\t[file size $file.map] bytes"
    }
    # result:
    #   uncompressed  1041 bytes
    #   compressed  153 bytes

Voir aussi


Discussion


Catégorie Exemple | Catégorie Traitement d'image