Category: algorithm

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.

(more…)

2019年1月25日

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算法首先要了解一些概念：

字符串前缀，真前缀，后缀，真后缀，及前缀函数

举个例子，如字符串 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

}

参考文章：

堆排序

关键：k[i]>=k[2i]&&k[i]>=k[2*i+1] 父节点大于子节点这是大根堆。

堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）

利用堆排序，分两步：

1构建堆

2获取堆顶

package main

import (
   "fmt"
)

func main() {
   arr := []int{0, 1, 2, 3, 4, 5, 6, 7}

   for length := len(arr); length > 0; length-- {
      buildBigHeap(arr, length)
      fmt.Print(arr)
      change(&arr[0], &arr[length-1])
      fmt.Print("***")
      fmt.Print(arr)
      fmt.Println("-----------")
   }

}

/**
建立大顶堆
 */
func buildBigHeap(arr []int, len int) {
   //for parent node
   //k[i]>=k[2i]&&k[i]>=k[2*i+1]

   count := 0
   for to := len - 1; to > 0; to-- {
      node := to
      for parent := obtainParent(node); node > 0; node, parent = parent, obtainParent(node) {
         if arr[parent] < arr[node] {
            change(&arr[parent], &arr[node])
            count++
         }
      }
   }
   fmt.Println(count)
}

func change(a *int, b *int) {
   temp := *a;
   *a = *b
   *b = temp
}

/**
获取父节点下标
 */
func obtainParent(child int) int {
   //数组下标从1开始
   //parent=node/2
   //从0开始
   //parent+1=(node+1)/2==>parent=(node+1)/2-1

   return (child+1)/2 - 1
}

2017年10月22日

Category: algorithm

file deduplication

File system-based deduplication

kmp匹配字符串

堆排序