技术

正则表达式

Python中的正则表达式

实际编程开发中，会遇到很多字符串处理相关的工作，因此专为处理匹配字符串的正则表达式一定需要花时间学习的。

基础表达

我们以匹配一个简单的邮箱*liangzelang@gmail.com*为例介绍正则表达式的入门方法。

基本元素表达

  • \w表示匹配一个字母或数字
  • \d表示匹配一个数字
  • \s表示匹配一个空格
  • .表示匹配任意字符

基本数量表达

有了上述的基本表达，那么我们可以看一下如果匹配不同数量的字符

  • +表示一个或以上的字符，如\d+表示匹配一个或以上的数字字符串，可以匹配1和123456
  • *表示任意个字符，可以是0个，如\w*表示匹配任何个字母或数字
  • ?表示0个或1个字符，如<?liangzelang>?表示匹配liangzelang 或 <liangzelang>
  • {n}表示n个字符，同时可以限定数量范围{m,n},表示m–n个字符

特殊字符表达

  • \转义符，实际工作中会用到很多特殊字符* . ? + $ ^ [ ] ( ) { } | \ /等，这个时候需要加上\转义符

了解了上面的基本表达可以顺利写出邮箱的正则表达式：
\w+@\w+\.\w+ ,为了更直观python的用例如下：

进阶表达

匹配192.168.1.1这个IP地址，可以容易得到\d+\.\d+\.\d+\.\d+,但是这样有个问题就是如果是999.999.999.999也匹配上了,因此我们需要匹配的更加准确

精确范围表达

  • []表示匹配的字符串范围，如[0-9A-Za-z]表示一个数字或者字母
  • ^表示匹配字符串起始
  • $表示匹配字符串结尾
  • [A|B]表示匹配A或者B
    那么正则表达式'^[2[0-5][0-5]|1[0-9][0-9]|[0-9]?[0-9][\.]?]{4}$' 可以匹配192.168.1.1

python re库

以上就是在python中使用正则表达式的基础知识，python中有专门的正则表达式库re,该库主要包含一些处理正则表达式的函数接口：
re模块相关API接口

匹配正则表达式 re.match

以上文讲到的匹配email地址：

1
2
3
4
5
6
import re

if re.match(r'\w+@\w+\.\w+', 'liangzelang@gmail.com'):
    print("OK")
else:
    print("not match")

匹配IP地址：

1
2
3
4
5
6
import re

if re.match(r'^[2[0-5][0-5]|1[0-9][0-9]|[0-9]?[0-9][\.]?]{4}$', '192.168.1.1'):
    print("IP ok")
else:
    print("IP not match")

切分字符 re.split

如果使用正常的字符串切分函数是无法去除多余的字符或者空格的：

1
2
>>> 'a b  c'.split(' ')
['a', 'b', '', 'c']

使用re.split函数：

1
2
3
>>> import re
>>> re.split(r'\s+', 'a b  c')
['a', 'b', 'c']

分组

上文中我们匹配了邮箱和IP，那如果我们要找到邮箱中对应的用户名、邮箱服务商或者IP地址的网段，那么就需要把匹配到的字符串分组；

  • ()表示需要提取的分组

re.match函数返回的Match对象正好有group方法可以提供匹配到每个分组字符串。
match对象的方法

1
2
3
4
5
6
7
8
9
10
11
12
>>> import re
>>> m = re.match(r'^(\w+)@(\w+)\.(\w+)$', 'liangzelang@gmail.com')
>>> m
<re.Match object; span=(0, 21), match='liangzelang@gmail.com'>
>>> m.group(0)
'liangzelang@gmail.com'
>>> m.group(1)
'liangzelang'
>>> m.group(2)
'gmail'
>>> m.group(3)
'com'

编译 re.compile

实际使用中一般先编译正则表达式，可以确保正则表达式本身没有语法错误，然后再使用编译后的正则表达式直接匹配使用。如果反复使用效率会有较大提升。

1
2
3
4
5
>>> re.compile(r'^(\w+)@(\w+)\.(\w+)$')
re.compile('^(\\w+)@(\\w+)\\.(\\w+)$')
>>> email = re.compile(r'^(\w+)@(\w+)\.(\w+)$')
>>> email.match('liangzelang@gmail.com').groups()
('liangzelang', 'gmail', 'com')

参考

Linux正则表达式

  • 未完待续
技术

[5. 最长回文子串] C + 中心扩展 + 暴力

Leetcode No.5

  • 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例:

1
2
3
4
5
6
7
8
9
10
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

return [0, 1].

result

解题思路

  1. 没有思路，只有暴力解，以每个点为中心向两边扩散；
  2. 但是条件1中又需要考虑奇数偶数的情况，原本想的是每次传个left和right，但是题解搞了一种骚操作，就是通过中心点i和长度len，直接求出left和right

复杂度分析

时间复杂度： O(n^2)
空间复杂度： O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//start: 19:35
// 解前思路：没啥思路，弱点就在字符串这块，难，先暴力一下：以每个点作为中心点来判断
#define MAX(x, y) (x > y) ? x : y
int loopPalindrome(char* s, int l, int r) {
    if (r >= strlen(s)) return 0;
    int len = 0;
    while (l >= 0 && r <= strlen(s) && s[l] == s[r]) {
        l--;
        r++;
        len = r - l - 1;
    }
    return len;
}

char * longestPalindrome(char * s){
    if (s == NULL) return NULL;
    int r = 0;
    int l = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        int len1 = loopPalindrome(s, i, i);
        int len = loopPalindrome(s, i, i + 1);
        int maxLen = MAX(len1, len);
        if (maxLen > (r - l + 1)) {
            l = i - (maxLen - 1) / 2;
            r = i + maxLen / 2;
        }
    }
    char* res = (char*)malloc(sizeof(char) * (r - l + 2));
    memcpy(res, &s[l], (r - l + 1));
    res[r - l + 1] = '\0';
    return res;
}

作者：liangzelang
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5-zui-chang-hui-wen-zi-chuan-c-zhong-xin-kuo-zhan-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
技术

数据结构之图论基础

1、图的数据存储

1.1、 邻接矩阵

图的邻接矩阵是由两个数组完成，一个一维数组存储图中的顶点;一个二维数组存储图中的边或弧。
如果图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
arc[i][j]等于1（如果（Vi，Vj）属于E），反之等于0。
有向图也差不多，有了出度和入度的概念
网 就是有权的图

邻接矩阵的创建

Read More

技术

Caffe ResNet50微调

背景介绍

最近在学习Caffe，但是周围没有人交流，很是吃力，故分享之，如果有错误大家一定要指出，也希望对其他人有一定帮助。
ResNet模型是在2015年KaiMingHe提出来的，一举夺得了2015的ILSVRC ImageNet分类、识别、 定位的冠军（太腻害）。这个网络结构的特点就是没有最深只有更深……，在作者的github上，有相应的代码，大家如果感兴趣可以看看。
我介绍一下我的数据，最近参加一个百度的比赛，100类宠物狗的识别。数据集一共18000张左右，但是数据质量一般，大小不定。最开始直接使用数据train from scratch，采用AlexNet错误率63%。我也是深度学习的初学者(水平就是看了一本书，看了一遍代码，跑了一遍例程)，所以决定go deeper，实验室服务器GPU是Tesla T40m可以跑一个稍微大一点的网络，所以选择ResNet50,顾名思义就是只有50层的残差网络。具体的网络结构图如图所示。使用ImageNet的pretrain模型进行finetune。我之前不太懂，直接拿18000张数据丢到网络中，过拟合严重，原因就是数据对于这种大型网络实在太少。（这其实也是技术交流的重要性，你自己搞一周，高手一句话可能就够了^_^）

Caffe ResNet50 Finetune

我使用的是KaiMing He大神GitHub中的模型和相关配置
这是作者ResNet的repo，里面有预训练模型、网络定义等. ResNet
其中有一个50层的ResNet caffemodel，一个deploy.prototxt。需要从one drivedown下来，非常慢，也可以在百度云下载到caffemodel。
因此需要自己做的工作有：

  1. 写一个train_val.prototxt配置文件，从deploy.prototxt改一下就OK
  2. 修改train_val.prototxt一些参数
  3. 准备数据集，最好转换为LMDB，速度能提高很多

具体实现步骤

train_val.prototxt

直接复制deploy.prototxt,然后修改。

  1. 加入数据层
  2. 根据自己的任务，修改最后全连接层的输出类别数量，我的为100. num_output: 100
  3. 在训练阶段把BN层中 ‘use_global_flag: false’ 全部设置为false，测试阶段全部设置为 true，所以这个实现需要分开写，然后用参数’include{ phase: train/test}’指明是啥阶段，我觉得这样有点麻烦，所以我是train.prototxt和test.prototxt分开写的，具体的见我的github
  4. 修改最后全连接层的名字、学习率，因为要重新根据我们自己的任务训练最后的全连接层，故不能使用pretrained model对应的名字，这样这层参数将被随机初始化，重新训练；学习率提高可以较快训练这一层。
    这样训练和测试的网络结构文件就搞定了。

solver.prototxt

这个主要配置一些训练参数，例如学习率什么的，也是根据自己的任务、数据来动态调节的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
train_net: "examples/fusion/f1/train.prototxt"                                  
test_net: "examples/fusion/f1/test.prototxt"
# iter_size: 2
test_iter: 3000
test_interval: 365
# ture: run from lastest snapshot, false: run from iteration 0
# test_initialization: false
display: 365
base_lr: 0.001
lr_policy: "multistep"
# 5th epoch  0.0001
stepvalue: 2920
# 10th epoch 0.00001
stepvalue: 9125
# 20th epoch 0.000001
stepvalue: 21900
# 40th epoch 0.0000001
stepvalue: 31025
# 80th epoch 0.00000001
# stepvalue: 36640
gamma: 0.1
max_iter: 36500
momentum: 0.9
weight_decay: 0.0001
snapshot: 1000
snapshot_prefix: "examples/fusion/f1/f1"
solver_mode: GPU

deploy.prototxt

这个是最后使用训练得到的模型来进行分类的网络结构，其实跟test.prototxt差不多，我需要分类的是图片，所以就把test.prototxt的数据层改一下，loss和acc层改一下就可以啦。

训练

1
2
3
4
5
6
7
###################                                                             
# author:liangzelang
# resnet50 train shell scripts
####################
#!/usr/bin/env sh
./build/tools/caffe train \
    --solver=examples/fusion/f1/solver.prototxt -weights examples/fusion/f1/resnet50.caffemodel

END

技术

目标跟踪之TLD第一篇

目标跟踪之TLD（Tracking-Learning-Detection）–第一篇

之前总结了目标跟踪领域的一些传统方法，光流、meanshift、camshift等，这些大概都是2010之前比较流行的方法。都是比较纯粹的跟踪方法，有很多需要完善的东西，比如camshift虽然对跟踪目标的形变不敏感，但是如果在目标与背景颜色相差不大的情况，跟踪效果很差；传统方法在跟踪目标消失或者被完全遮挡后，再出现无法进行准确的重新跟踪（其实也可以，就是依靠相关的目标检测方法啦）。

今天要介绍的方法就是在2012年Kalal的TLD方法，主要是长时间跟踪的一种方法，把检测、跟踪、学习融合在一起。
OpenCV3.2.0已经加入了TLD算法，但是我目前的版本是2.4,所以今天这个TLD的实现是Github上面的大神实现的。稍后也会加上OpenCV上面的TLD效果。

Read More

技术

目标跟踪之OpticalFlow

OpticalFlow 光流法

在视频序列中，把视频帧中每个像素与速度相关联，或者与同一像素点两帧之间的位移相关联，那么我们就可以得到稠密光流。Horm-Schunck方法是计算光流的速度场。OpenCV是计算两帧之间对像素领域匹配，也叫块匹配；两种方法都是稠密跟踪。但是计算量都不小，所以不重点介绍。

Lucas—Kanada光流法

相比上面的稠密光流，伟大的前人搞出了稀疏光流法，就是找出一些合适跟踪的特征点来进行跟踪匹配，即减少了运算量，效果还不差。稀疏光流法中当属LK光流法最有名。

LK算法原理

Read More

技术

目标跟踪之meanshift/camshift

目标跟踪–meanshift和CamShift

之前讲过最简单的目标跟踪方法：模板匹配（其实是目标检测范畴），这个方法有很多局限。因此又产生了很多其他的目标跟踪方法，例如应用广泛的meanshift。
meanshift是一种在数据密度分布中寻找局部极值的稳定的方法，对数据的密度直方图引用爬山算法即可。1998年的时候，人们开始把这种数据寻优的算法应用于图像的目标跟踪领域。
OpenCV也实现了这个算法，大致过程就是：

  1. 选择跟踪的区域
  2. 计算跟踪区域直方图的概率分布(这里可以选择颜色+纹理的特征进行反向投影)
  3. 计算新一帧图像的概率分布
  4. 运用meanshift算法计算目标新中心

跟踪效果

Read More

技术

数据结构之链表-队列-串

其实在编程中，简单的链表、队列等都构成所有复杂算法、复杂数据结构的基础。因此我们了解了这些数据结构基础，对于那些复合而成的数据结构也就自然明白。

1、链表

顺序表是一种按照某种规则排列在一起的表，它有两种存储方式：一是表元素全部依次相邻存储（顺序存储结构）这里就不详细介绍顺序存储结构了；一是表元素可以放在任意位置，由相应指针指明其相邻元素位置（链式存储），所以也叫链表。
链表也分单链表、双链表、循环链表。

Read More

技术

数据结构之树

树的相关概念

树在数据结构中非常重要，应用也有很多。下面只记录一些重要的、基础性的概念。

  • 结点：树由结点构成的，有根节点、叶结点等。结点有用的子树数就是结点的度，叶结点度为0.同一个父节点的结点互为兄弟，跟人一样，就不介绍，有点弱智的感觉。
  • 树的深度： 树的根层次为1，根的子结点层次为2，依次类推。树中结点的最大层次即为树的深度或者高度。

树的存储结构和实现

在上面概念中说了树中的结点关系和人一样，树的存储就是把这些结点关系存起来。根据人的经验，从不同角度介绍某个人的方式是不一样的，介绍你亲姐：这是我姐，这是我父母的女儿……数的存储和实现也一样。

  1. 双亲表示法 |data|parent|

    Read More