Google Reader 导出数据搜索预览小工具

2011年11月02日 15:06

updated at 2013/3/14: R.I.P Google Reader.

Google Reader改版了,是好是坏众说纷纭,总之原来那些分享的文章变成冷冰冰的数据包了。在Google悔过之前,我们总不能对着这一个个数据包发呆吧,特别是突然想找什么老文章的时候。所以在大牛 @isnowfy 的启示下有了这个小工具^_^

需要说明的是针对的是“阅读器 JSON”这种数据包,比如 shared-items.json 和 starred-items.json。搜索框里回车可以对标题进行搜索,列表框里单击可以在右侧看到详细信息,比如url地址和去html标签后的网页内容。去html标签使用了BeautifulSoup,所以请自备 BeautifulSoup.py在同一目录下 BeautifulSoup4。由于对Tk(Tkinter)这个古老而恶心的GUI不熟悉,界面上请不要苛责了^_^

附上使用图片和脚本:
reader.png

# coding: utf-8
import json
from Tkinter import *
import tkFileDialog
from bs4 import BeautifulSoup

root = Tk()
e = StringVar()
li, te, data, items = [None]*4
sanitize_all_html = lambda value: BeautifulSoup(value).get_text()


def selectFile():
    global data, items
    filename = tkFileDialog.askopenfilename(parent=root, initialdir='.',
                                            filetypes=[('GR data', '.json')])
    data = json.load(open(filename))
    items = data['items'] if 'items' in data else data
    items = filter(lambda i: 'title' in i, items)
    filterItems()


def filterItems(event=None):
    global data, items
    li.delete(0, END)
    s = e.get()
    for i in items:
        title = i['title']
        try:
            content = ('summary' in i and i['summary']
                                       or i['content'])['content']
        except:
            content = ''
        if s in title or s in content:
            li.insert(END, title)


def showItemInfo(event=None):
    te.delete(1.0, END)
    title = li.get(li.curselection())
    item = filter(lambda i: i['title'] == title, items)[0]
    te.insert(1.0, item['title']+'\n')
    te.insert(2.0, ('author' in item and item['author'] or 'NO AUTHOR')+'\n')
    te.insert(3.0, item['origin']['title']+'\n')
    te.insert(4.0, item['origin']['htmlUrl']+'\n')
    te.insert(5.0, ('alternate' in item and item['alternate'][0]['href'] or
                    'NO URL')+'\n\n')
    if 'summary' in item:
        te.insert(7.0, sanitize_all_html(item['summary']['content'])+'\n')
    else:
        te.insert(7.0, sanitize_all_html(item['content']['content'])+'\n')

f = Frame(root)
lf = Frame(f)
rf = Frame(f)
f.pack(fill='both', expand=1)
lf.pack(side='left', fill='both')
rf.pack(side='left', fill='both', expand=1)

fbt = Button(lf, text="Select file", height=1, command=selectFile)
fbt.pack(side='top', fill=X)

en = Entry(lf, textvariable=e, width=30)
en.bind('<Return>', filterItems)
en.pack(side='top', fill=X)

liy = Scrollbar(lf, orient=VERTICAL)
li = Listbox(lf, yscrollcommand=liy.set)
li.bind('<<ListboxSelect>>', showItemInfo)
liy['command'] = li.yview
li.pack(side='left', fill='both', expand=1)
liy.pack(side='left', fill=Y)

tey = Scrollbar(rf, orient=VERTICAL)
te = Text(rf, yscrollcommand=tey.set, height=30,
          font=('Microsoft Yahei', '12'))
tey['command'] = te.yview
te.pack(side='left', fill='both', expand=1)
tey.pack(side='left', fill=Y)

root.title('GR Data Reader')
root.mainloop()

评论(0) 阅读(1939)

poj 2117 求割点的tarjan算法

2011年10月20日 17:43

大四真闲,也不突击比赛了,可以拿出大把的时间慢慢看点儿算法,研究一下证明,tarjan大神的三个图论算法总算是都了解了。

割点是无向图中去掉后能把图割开的点。dfs时用dfn(u)记录u的访问时间,用low(u)数组记录u和u的子孙能追溯到的最早的节点(dfn值最小)。由于无向图的dfs只有回边和树边,且以第一次dfs时的方向作为边的方向,故有:
low=min{
dfn(u),
dfn(v),若(u,v)为回边(非树边的逆边)
low(v),若(u,v)为树边
}

顶点u是割点当且仅当其满足(1)或者(2):
(1) 若u是树根,且u的孩子数sons>1。因为没有u后,以这些孩子为根的子树间互相就不连通了,所以去掉u后得到sons个分支。
(2) 若u不是树根,且存在树边(u,v)使 low(v)>=dfn(u)。low值说明以v为根的子树不能到达u的祖先也就是去掉u后不能和原图联通,所以得到{这样的v的个数+1}个分支。

这个题是求无向图(不一定联通)中,去掉一个顶点可以形成的最多的分支数,对所有分支tarjan一下就知道了去掉哪个多了,注意孤立点的情况。求low时其实不用判断树边的逆边的情况,仔细琢磨一下,对结果没有影响,又能省很多代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn];
int dfn[maxn],low[maxn];
bool vit[maxn];
int n,idx,sons;
int ans;

void dfs(int u,bool root)
{
    vit[u]=1;
    dfn[u]=low[u]=++idx;
    int child=0;
    for(it i=g[u].begin();i!=g[u].end();++i)
    {
        int v=*i;
        if(!dfn[v])
        {
            dfs(v,false);
            low[u]=min(low[u],low[v]);
            if(root)
                sons++;
            else if(low[v]>=dfn[u])
                child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    ans=max(ans,child+1);
}

int tarjan(int root)
{
    if(g[root].size()==0) return 0;
    memset(dfn,0,sizeof(dfn));
    ans=idx=sons=0;
    dfs(root,true);
    if(sons>1) ans=max(ans,sons);
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF && n)
    {
        for(int i=0;i<n;i++)
            g[i].clear();
        while(m-->0)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(vit,0,sizeof(vit));
        int ma=0,total=0;
        for(int i=0;i<n;i++)
            if(!vit[i])
                total++,ma=max(ma,tarjan(i));
        printf("%d\n",total+ma-1);
    }
}

评论(0) 阅读(4905)

斯坦福在线人工智能课程字幕下载脚本

2011年10月12日 20:42

updated at 2011.11.02: 根据留言问题更新了一下脚本
updated at 2011.12.13: youtube改版, 改一下第一个脚本中某个正则

提供一种思路哈,方便离线看的童鞋~

批量下载youtube视频可以用firefox的插件BYTubeD~

字幕批量下载的步骤(firefox中):

1.选中youtube网页中那一堆视频的缩略图,右键选"查看选中部分源代码",存为in.txt,用下面的脚本正则出视频地址和名字:

# coding: utf-8
import sys,re

urlpattern  =re.compile(r'watch\?v=([^\"]*)\" class=\"ux-thumb')
#titlepattern=re.compile(r'title=\"([^\"]*)\"')
titlepattern=re.compile(r'video-title\">([^\<]*)\<')
timepattern =re.compile(r'video-time\">(\d+:\d+)')

# in.txt is a part of the source file of the youtube page !!!
content=file('in.txt').read().split('\n')
allurl=[]
alltitle=[]
alltime=[]
for line in content:
    allurl+=urlpattern.findall(line)
    alltitle+=titlepattern.findall(line)
    alltime+=timepattern.findall(line)
print "Found:",len(alltime),len(allurl),len(alltitle)
fo=file('urlinfo.txt','w')
sys.stdout=fo
allinfo=zip(allurl,alltitle,alltime)
for info in allinfo:
    for i in info:
        print i
    print ''
fo.close()

2.对于上面的脚本生成的urlinfo.txt文件,用下一个脚本下载所有的xml格式的英文字幕,其中用到了http代理:

import os,urllib2
 
proxy_handler = urllib2.ProxyHandler({"http" : 'http://127.0.0.1:8123'})
opener = urllib2.build_opener(proxy_handler)
urllib2.install_opener(opener)

#baseurl='http://www.youtube.com/api/timedtext?v=%s&name=English%%20via%%20dotsub&lang=en&hl=en'
baseurl='http://www.youtube.com/api/timedtext?asr_langs=en%%2Cja&caps=asr&v=%s&name=English%%20via%%20dotsub&lang=en'
urlinfo=file('urlinfo.txt','r').read().split('\n')
cnt=len(urlinfo)
print 'Total:',cnt/4

for i in range(0,cnt-1,4):
    try:
        print 'Start',i,urlinfo[i+1]
        if os.path.exists(urlinfo[i+1]+'.xml'):
            continue
        fo=file(urlinfo[i+1]+'.xml','w')
        print 'getting:',baseurl % urlinfo[i]
        fo.write(urllib2.urlopen(baseurl % urlinfo[i]).read())
        fo.close()
        print 'Done ',i
    except Exception,e:
        print e.message
        pass

3.用下面的脚本把xml格式的字幕转换为srt格式的:

# coding: utf-8

import os,re
stamppattern=re.compile(r'start=\"(\d+)\.?\d*\" dur=\"(\d+)\.?\d*\"')
textpattern =re.compile(r'dur=\"\d+\.?\d*\">(.*)$')

def second2time(sec):
    ret=[]
    ret.append(sec/60/60)
    ret.append(sec/60)
    ret.append(sec%60)
    return ret

def xml2srt(data,fo):
    data=data.split('</text>')
    data=data[:-1]
    for i,line in enumerate(data):
        fo.write('%d\n' % (i+1))
        stamps=map(int,stamppattern.findall(line)[0])
        fo.write('%02d:%02d:%02d,000 --> %02d:%02d:%02d,000\n' % tuple(second2time(stamps[0])+second2time(stamps[0]+stamps[1])))
        fo.write(textpattern.findall(line)[0]+'\n\n\n')

if __name__=='__main__':
    fs=filter(lambda s:s.endswith('.xml'),os.listdir('.'))
    for f in fs:
        if os.path.exists(f[:-4]+'.srt'): continue
        print f[:-4],'ON!'
        fo=file(f[:-4]+'.srt','w')
        xml2srt(file(f,'r').read(),fo)
        fo.close()
        print f[:-4],'Done'

4.最后一步把字幕里的html标记替换掉:

# coding: utf-8

import os,re
def all_mark():
    markpattern=re.compile(r'&amp;[^;]*;')
    allmarks=set()

    fs=filter(lambda s:s.endswith('.srt'),os.listdir('.'))
    for f in fs:
        marks=markpattern.findall(file(f,'r').read())
        allmarks=allmarks.union(set(marks))
    return allmarks
    # set(['&amp;quot;', '&amp;#39;', '&amp;gt;', '&amp;lt;'])

if __name__=='__main__':
    fs=filter(lambda s:s.endswith('.srt'),os.listdir('.'))
    for f in fs:
        content=file(f,'r').read()
        content=content.replace('&amp;quot;','"')
        content=content.replace('&amp;#39;',"'")
        content=content.replace('&amp;gt;','>')
        content=content.replace('&amp;lt;','<')
        fo=file(f,'w')
        fo.write(content)
        fo.close()
    print 'Unreplace marks:',str(all_mark())

5.调整字幕时间,把上一条字幕的结束时间设为下一条字幕的开始时间

# coding: utf-8

import os,re

if __name__=='__main__':
    fs=filter(lambda s:s.endswith('.srt'),os.listdir('.'))
    for f in fs:
        content=file(f,'r').read().split('\n')
        n=len(content)/5
        for i in range(n-1):
            nextst=content[i*5+6][0:12]
            content[i*5+1]=content[i*5+1][0:17]+nextst
        of=file(f,'w')
        of.write('\n'.join(content))
        of.close()

评论(3) 阅读(2988)

斯坦福在线机器学习课程字幕下载脚本

2011年10月11日 10:40

updated at Oct. 2012: 字幕打包下载 http://dl.vmall.com/c00blsic2a

斯坦福在线机器学习(Machine Learning)课程终于在昨天(10月10号)开课了,网址在 http://www.ml-class.org

和AI课程的视频放在youtube上不同,ML的在线视频提供下载,但是下载的版本没有英文字幕,故此放出自产自用字幕下载脚本,仿照以前的豆瓣电台歌曲信息脚本,也是从firefox获得cookie,然后爬得xml的字幕,再转换为srt格式的,这样就可以离线或者在iPad上看了!^_^

第一个是偷firefox的cookie爬网页,下载xml版的脚本,注意修改其中的firefox的cookie文件的目录,需要安装pysqlite包:

# coding: utf-8

import cookielib,urllib2
from cStringIO import StringIO
from pysqlite2 import dbapi2 as sqlite
import re,os

# a useful function from others
def sqlite2cookie(filename,host):
    con = sqlite.connect(filename)
    con.text_factory = str
    cur = con.cursor()
    cur.execute("select host, path, isSecure, expiry, name, value from moz_cookies where host like ?"
            ,['%%%s%%' % host])
    ftstr = ["FALSE","TRUE"]
    s = StringIO()
    s.write("""\
# Netscape HTTP Cookie File
# http://www.netscape.com/newsref/std/cookie_spec.html
# This is a generated file! Do not edit.
""")
    for item in cur.fetchall():
        s.write("%s\t%s\t%s\t%s\t%s\t%s\t%s\n" % (
            item[0], ftstr[item[0].startswith('.')], item[1],
            ftstr[item[2]], item[3], item[4], item[5]))
    s.seek(0)
    #print "cookie:",s.read() ;s.seek(0)
    cookie_jar = cookielib.MozillaCookieJar()
    cookie_jar._really_load(s, '', True, True)
    return cookie_jar

# get cookie
cookiejar = sqlite2cookie(r'C:\Users\lenovo\AppData\Roaming\Mozilla\Firefox\Profiles\osfuexqh.default\cookies.sqlite','ml-class.org')
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cookiejar))
urllib2.install_opener(opener)

# post cookie
print 'Getting page, if it takes too long time, kill me!'
content=urllib2.urlopen('http://www.ml-class.org/course/video/list?mode=view').read()
#print content
content=''.join(content.split('\n'))
print "Page got!"

# get file name
namefinder=re.compile(r"file: ([^,]*),")
found=namefinder.findall(content)
print 'Number of files:',len(found)
found=map(lambda s: s[1:-1],found)
#print found

# down xml
baseurl='http://s3.amazonaws.com/stanford_videos/cs229/subtitles/%s-subtitles.xml'
for i,fn in enumerate(found):
    fn=fn.replace(r'\'','\'')
    outfile=fn+'.xml'
    if os.path.exists(outfile):
        continue
    print 'Getting:',fn
    fo=file(outfile,'w')
    fo.write(urllib2.urlopen(baseurl % fn).read())
    fo.close()
    print 'Done:',i,outfile

第二个是批量把xml脚本转化为srt字幕文件的脚本,各种字符串处理比较挫,见笑了:

# coding: utf-8
import os,sys,re,codecs

limit=[60,60,60,1000]
def xml2srt(fi,fo):
    data=''.join((fi.read().split('\n')[9:-4])).strip().split('</p>')
    for i in range(0,len(data)-1):
        #print i,data[i]
        if data[i]:
            st_st=data[i].index('"')
            st_ed=data[i].index('"',st_st+1)
            if i+1<len(data)-1:
                nx_st=data[i+1].index('"')
                nx_ed=data[i+1].index('"',nx_st+1)
            fo.write(str(i+1)+' \n')
            stamps=[data[i][st_st+1:st_ed],
                    data[i+1][nx_st+1:nx_ed] if i+1<len(data)-1 else "99:59:59.999"]
            word=data[i][data[i].index('>')+1:].replace('\n',' ')+' \n\n\n'
            for i,stamp in enumerate(stamps):
                stamp=stamp.split('.')
                stamps[i]=map(int,stamp[0].split(':'))
                stamps[i].append(int(stamp[1]))
            stamps=map(lambda s:"%02d:%02d:%02d,%03d" % tuple(s),stamps)
            fo.write("%s --> %s \n" % tuple(stamps))
            fo.write(word)
    #print 'OK!'

if __name__=='__main__':
    for fn in os.listdir('.'):
        if fn[-4:]!='.xml':
            continue
        print 'Converting:',fn[:-4]
        fi=file(fn,'r')
        if os.path.exists(fn[:-4]+'.srt'):
            continue
        fo=file(fn[:-4]+'.srt','w')
        xml2srt(fi,fo)
        fo.close()
        print 'Done'

感谢wr大牛(@isnowfy)的支持,附上wr大牛的单个字幕下载的简化版本,还有exe可执行文件哦!

评论(2) 阅读(6512)

LCA的tarjan算法的理解

2011年10月08日 11:08

tarjan算法的步骤是(当dfs到节点u时):
1 在并查集中建立仅有u的集合,设置该集合的祖先为u
1 对u的每个孩子v:
   1.1 tarjan之
   1.2 合并v到父节点u的集合,确保集合的祖先是u
2 设置u为已遍历
3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先
 
举例说明(非证明):


假设遍历完10的孩子,要处理关于10的请求了
取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10
集合的祖先便是关键路径上距离集合最近的点
比如此时:
    1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
    3,7为一个集合,祖先为3,集合中点和10的LCA为3
    8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
    10,12为一个集合,祖先为10,集合中点和10的LCA为10
你看,集合的祖先便是LCA吧,所以第3步是正确的
道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点

为什么要用祖先而且每次合并集合后都要确保集合的祖先正确呢?
因为集合是用并查集实现的,为了提高速度,当然要平衡加路径压缩了,所以合并后谁是根就不确定了,所以要始终保持集合的根的祖先是正确的
关于查询和遍历孩子的顺序:
wikipedia上就是上文中的顺序,很多人的代码也是这个顺序
但是网上的很多讲解却是查询在前,遍历孩子在后,对比上文,会不会漏掉u和u的子孙之间的查询呢?
不会的
如果在刚dfs到u的时候就设置u为visited的话,本该回溯到u时解决的那些查询,在遍历孩子时就会解决掉了
这个顺序问题就是导致我头大看了很久这个算法的原因,也是絮絮叨叨写了本文的原因,希望没有理解错= =

最后,为了符合本blog风格,还是贴代码吧:

int f[maxn],fs[maxn];//并查集父节点 父节点个数
bool vit[maxn];
int anc[maxn];//祖先
vector<int> son[maxn];//保存树
vector<int> qes[maxn];//保存查询
typedef vector<int>::iterator IT;

int Find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=Find(f[x]);
}
void Union(int x,int y)
{
    x=Find(x);y=Find(y);
    if(x==y) return;
    if(fs[x]<=fs[y]) f[x]=y,fs[y]+=fs[x];
    else f[y]=x,fs[x]+=fs[y];
}

void lca(int u)
{
    anc[u]=u;
    for(IT v=son[u].begin();v!=son[u].end();++v)
    {
        lca(*v);
        Union(u,*v);
        anc[Find(u)]=u;
    }
    vit[u]=true;
    for(IT v=qes[u].begin();v!=qes[u].end();++v)
    {
        if(vit[*v])
            printf("LCA(%d,%d):%d\n",u,*v,anc[Find(*v)]);
    }
}

ref:
http://purety.jp/akisame/oi/TJU/
http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm
http://techfield.us/blog/2008/11/lowest_common_ancester_tarjan_alogrithm/

评论(9) 阅读(17990)