Base64

Base64

所谓Base64,就是说选出64个字符—-小写字母a-z、大写字母A-Z、数字0-9、符号”+”、”/”(再加上作为垫字的”=”,实际上是65个字符)—-作为一个基本字符集。然后,其他所有符号都转换成这个字符集中的字符。
Base64将三个字节转化成四个字节,因此Base64编码后的文本,会比原文本大出三分之一左右。

Base64 Table

Index Char Index Char Index Char Index Char
0 A 16 Q 32 g 48 w
1 B 17 R 33 h 49 x
2 C 18 S 34 i 50 y
3 D 19 T 35 j 51 z
4 E 20 U 36 k 52 0
5 F 21 V 37 l 53 1
6 G 22 W 38 m 54 2
7 H 23 X 39 n 55 3
8 I 24 Y 40 o 56 4
9 J 25 Z 41 p 57 5
10 K 26 a 42 q 58 6
11 L 27 b 43 r 59 7
12 M 28 c 44 s 60 8
13 N 29 d 45 t 61 9
14 O 30 e 46 u 62 +
15 P 31 f 47 v 63 /

Continue reading “Base64”

file deduplication

File system-based deduplication

File system-based deduplication is a simple method to reduce duplicate data at the file level, and usually is just a compare operation within the file system or a file system-based algorithm that eliminates duplicates.

An example of this method is comparing the name, size, type and date-modified information of two files with the same name being stored in a system.

If these parameters match, you can be pretty sure that the files are copies of each other and that you can delete one of them with no problems. Although this example isn’t a foolproof method of proper data deduplication, it can be done with any operating system and can be scripted to automate the process, and best of all, it’s free.

Continue reading “file deduplication”

kmp匹配字符串

 

kmp算法常用于优化字符串匹配,例如下面的问题:

有一个字符串a = “BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串b = “ABCDABD”

一般的做法是循环比较。

func contain(a string, b string) bool {
  for i := 0; i < len(a); i++ {
    k := i
    for j := 0; j < len(b); {
      if b[j] == a[k] {
        if j == len(b)-1 {
          return true
        }
        j++
        k++
      } else {
        //匹配失败
        j = 0
        break;
      }
    }
  }
  return false
}

可以看到耗时O(n*m),每一次失败都是从头逐个比较,特别对于ABCDAB多次重复匹配,kmp算法通过配置部分匹配表,减少这些重复匹配操作,从而达到优化效果。

KMP算法的精髓在于对已知信息的充分利用,理解kmp算法首先要了解一些概念:

  1. 字符串前缀,真前缀,后缀,真后缀,及前缀函数

举个例子,如字符串 ABCDABD,首先,不考虑空字符

前缀有A,AB,ABC,ABCD,ABCDA,ABCDAB,ABCDABD

真前缀有A,AB,ABC,ABCD,ABCDA,ABCDAB

同理可以理解后缀,真前(后)缀就是指不包含自身的前(后)缀

真后缀为BCDABD,CDABD,DABD,ABD,BD,D

“真前缀”指除了最后一个字符以外,一个字符串的全部头部组合;

“真后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

这里指的是真前缀后缀
   - "A"的前缀和后缀都为空集,共有元素的长度为0;
  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;zh
  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

前缀函数next[]是指某个字符串的最长真后缀同时也是它的前缀的子串长度。

array = {A, B, C, D, A, B, D}

next  = {-1, 0, 0, 0, 1, 2, 0}

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置.

/**
部分匹配表
 */
func prefixFunction(str string) []int {
  sLen := len(str)
  prefix := make([]int, sLen)

  i := 0
  for j := 1; j < sLen-1; j++ {

    if str[j] == str[i] {
      i++
      prefix[j] = i
    } else {
      i = 0
    }
  }

  return prefix
}

/**
转移数组
 */
func obtainMoveFromPrefix(prefix []int) [] int {
  sLen := len(prefix)
  move := make([]int, sLen)
  move[0] = -1;
  for i := 0; i < sLen; i++ {
    if i == 0 {
      move[0] = -1;
    } else {
      move[i] = prefix[i-1]
    }
  }
  return move
}


func contain(a string, b string) bool {
  m, n := len(a), len(b)
  move := obtainMoveFromPrefix(prefixFunction(b))

  j := 0
  for i := 0; i < m; i++ {

    //有匹配的字符
    for j > 0 && b[j] != a[i] {
      j = move[j]
      if j < 0 {
        j = 0
      }
    }
    if b[j] == a[i] {
      j++
    }
    if j == n {
      return true
    }
  }

  return false

}

参考文章:

kmp算法-wiki

字符串匹配的KMP算法

KMP 算法详细解析

从有限状态自动机的角度理解KMP算法