基于大模型的播客RAG系统搭建攻略(三):开源代码和后续计划

前文链接:

仓库地址https://github.com/liujinmarshall/podcast_rag

首先插播一条新闻。在两周之前,我常用的播客客户端小宇宙推出了会员plus计划:

我们的会员产品“小宇宙PLUS”现已上线,提供「AI播客总结」「收藏时点」「会员周报」「个性图标」「多彩主题色」等多个功能,一起来看看!

小宇宙PLUS会员,现已包含以下权益 ——

· AI播客总结
服务于播客重度用户的一些高信息密度节目场景。例如:你可以通过AI播客总结判断一期没有shownotes的节目是否值得听,也可以高效得到一期财经、商业、科技等领域节目的内容速报。更多使用场景,期待你的探索。

· 收藏时点
你可以通过「收藏时点」功能,随时标记最感兴趣的时点,记录此刻的私人笔记,并在【我的收藏】中查看汇总。即使正处于锁屏状态下也无需担心,iOS系统中,无需解锁也可以通过左下角的收藏按钮进行收藏时点的操作,一键收藏此刻的吉光片羽。

· 会员周报
每周一中午12:00左右,我们将为会员用户送上专属会员周报,并为你自动汇总并总结你可能错过的精彩节目,为你持续挖掘更多的兴趣内容。欢迎在【个人-会员入口】处进入查看。

· 个性图标与多彩主题色
看腻了你的小宇宙?成为小宇宙PLUS会员,即刻更换你的小宇宙图标和主题色,深空、毛绒、键帽、粉白、薄荷、深蓝……超多可选,让你的小宇宙与众不同。

当中第一项AI播客总结正好完美契合这个项目的功能,虽然我强烈怀疑这个会员是否真的值一年120元。因此我也在程序中加上了单集总结的功能。实现非常简单,通过发送提示词+播客转录稿实现。

计划中的功能列表:

  • 支持英文播客:加入英文提示词,并根据播客语言选择对应的提示词。
  • 切换embedding:现在使用的OpenAI text embedding的开销,对于个人用户来说不算很大,但也不小。需要切换到更便宜的版本或者本地推理的text embedding。目前计划使用MTEB榜单中排名较为靠前但显存需求不大的gte-Qwen2-1.5B-instruct
  • 一键运行所有任务:当前程序被分为不同的子程序,需要统一一个运行入口。
  • 新增播客总结:对于每次增量更新的内容进行小结。

以下是中文版的使用说明:

仓库地址https://github.com/liujinmarshall/podcast_rag

使用 RAG (检索增强生成) 技术来理解播客并提问

已测试 Python 版本:3.9 (应该也适用于更新的版本和不太旧的版本)

前提条件

  • Python 环境以及并了解如何运行 Python 程序
  • Google Gemini API 密钥和 OpenAI API 密钥

步骤

  1. 克隆此 Github 仓库;
  2. 创建一个名为 “data” 的目录;
  3. 将 podcasts.example.csv 复制到 data/podcasts.csv,并添加 RSS URL 条目;
  4. 通过 requirements.txt 安装 Python 依赖 (pip install -r requirments.txt);
  5. 将 Google Gemini API 密钥导出为 GEMINI_API_KEY,并将 OpenAI API 密钥导出为 OPENAI_API_KEY;
  6. 运行以下脚本以实现以下功能(使用 python xxx.py):
    1. download.py: 将播客音频媒体文件以增量模式下载到本地。每个播客一个目录。
    2. transcribe.py: 将音频媒体文件转录成文本。每个播客一个目录。
    3. index.py: 将转录文本分块并索引到向量数据库 (ChromaDB) 中。
    4. query.py: 启动一个聊天机器人来查询问题:
      • 运行程序;
        • 在浏览器中打开链接并开始提问 。
    5. summarize.py: 将转录文本总结成简洁的摘要。每个播客一个目录。
    6. delete_files.py: 删除音频媒体文件(超过 24 小时的文件),以防文件上传超出配额。上传超过 48 小时的文件将被自动清除

语言支持

  • 中文
  • 英语 (待添加)

注意

请遵守播客提供商的用户协议。此仓库仅供个人研究使用。

基于大模型的播客RAG系统搭建攻略(二):进阶之路与避坑指南

第一部分:https://onlymarshall.com/2025/01/05/build-personal-podcast-rag/

第三部分:https://onlymarshall.com/2025/01/26/build-personal-podcast-rag-part-3/

(注:本文在Gemini模型协助下完成。不得不感慨大模型很多时候思考的比人类周全,人类只要提供一些基本元素,大模型就可以把内容打磨地得非常完善)

上一篇我们介绍了播客搜索问答系统的基本架构和初步选型,特别是在语音转录方面的一些尝试和思考。今天我们继续深入,聊聊在系统搭建过程中遇到的更具体的技术挑战以及一些解决方案。

索引/检索的优化与挑战

上一篇我们提到索引和检索环节主要依赖文本向量模型和向量数据库。看似简单,但真正落地会遇到不少问题,尤其是在播客这种持续更新的内容源上。

增量更新:让知识库保持新鲜

播客的一大特点是持续更新。每周甚至每天都会有新的内容产生。如果每次更新都重新处理所有播客数据,那将是巨大的资源浪费。因此,增量更新是必须要考虑的。我们的目标是只处理新增的播客和更新的播客。这需要我们在“播客下载/爬虫”阶段做一些改进:

  • 记录已处理的播客和音频文件: 我们需要一个机制来记录哪些播客和对应的音频文件已经被处理过了。一个简单的做法是维护一个数据库(或者是简单的CSV文件),记录播客的feed URL以及每个episode的发布时间或唯一的GUID。
  • 对比更新时间或文件大小: 在爬取时,对于已经记录的播客,我们可以通过HEAD请求获取最新的episode信息,对比发布时间或GUID。对于新的episode,或者发布时间有更新的episode,再进行下载和后续处理。
  • 文件大小与HEAD请求的妙用: 除了对比发布时间,我们还可以利用HTTP HEAD请求来获取音频文件的大小。如果新爬取的音频文件大小与之前记录的不同,则说明文件可能被修改过,需要重新下载和处理。这对于一些播客会修改音频描述或者替换音频文件的情况很有用。HEAD请求相比于直接下载整个文件要高效得多,大大节省了网络资源。
  • 处理删除的播客: 有些播客可能会下架某集播客。我们需要定期检查已处理的播客列表,对比最新的feed内容,将已删除的播客集从向量数据库中移除,保持数据的一致性。
  • 保留时间:播客毕竟是音频文件,几百期的内容加起来也有几十个GB,如果总是保留所有的冷文件,特别是对于个人来说,存储的成本也没有必要。

有了以上这些功能,我们每天只要定时跑任务就可以自动完成对比、下载、转录、处理以及更新数据库的工作。

大模型转录的“后遗症”:重复文字问题

上一篇我们提到利用大模型的长上下文能力进行音频转录非常方便。但实际使用中,我们发现一个潜在的问题:重复文字和错误退出。

问题示例

尤其是在音频质量不高、语速较快或者多人对话的场景下,大模型有时会重复生成一些片段的文字。这可能是由于模型对音频的理解不够准确,或者在拼接长文本时出现偏差。

如何解决重复文字问题?

  • 检测错误并重新转录:这种情况有点像代码中因为并发造成的bug,而大模型运行本身也有一定的随机性,所以很大概率重新转录就可以解决这个问题。
  • 更精细的音频切分: 虽然我们避免了为了输入长度而进行的粗暴切分,但适当的、基于语义的切分仍然有必要。例如,可以根据静音段落或者明显的语意停顿进行切分,这样可以减少模型处理长音频的压力,降低重复的概率。
  • 后处理去重: 在得到转录文本后,可以进行一些后处理操作。例如,可以设定一个滑动窗口,如果窗口内的文本重复出现,则进行删除。当然,这需要谨慎操作,避免误删有效信息。
  • Prompt优化: 在给大模型下达转录指令时,可以加入一些提示,例如“请勿重复生成已出现过的文字”,虽然效果可能有限,但有时也能起到一定的作用。
  • 尝试不同的模型参数或模型: 不同的模型或者相同的模型在不同的参数设置下,表现可能会有差异。可以尝试调整解码策略或者使用更擅长处理此类问题的模型。

Text Embedding的中文选择:Gemini的踩坑

上一篇我们提到在文本向量模型上“跌了个跟头”。这里就来展开说说。

最初,我们可能自然而然地会选择一些通用的、在英文领域表现优秀的Embedding模型。既然Gemini也提供了文本Embedding,我们自然也选择这个模型。

但是在生成Embedding、存入数据库,再通过查询的Embedding进行检索之后,我发现了一个严重的问题:Gemini的文本模型似乎完全没办法理解中文

以下面的例子看,我们通过Gemini text-embedding-004模型,完全不同问题产生的embedding前10维完全一样。如果加上了一些英文字母的扰动,生成的结果就完全不一样。推测原因应该是tokenization的阶段把所有的非英文字符全部映射成了<UNK>,所以结果没有区别。

解决的方案也很简单:换成OpenAI的Embedding模型(text-embedding-3-small),因为使用了ChromaDB的代码,切换embedding function只要改动几行代码就可以实现。

后注:最终在某个文档页面发现了这个模型并不是多语言的版本,但似乎在GenAI embedContent的API里只能调用embedding-001和text-embedding-004,如果要调用多语言模型需要换到其他API。

Chunk大小的权衡

将长篇的转录文本切分成更小的chunk(块)是进行向量化的必要步骤。 Chunk的大小直接影响着检索的准确性和效率。

  • Chunk太小: 可能无法包含完整的语义信息,导致检索时丢失上下文,返回的结果不够相关。例如,一句关于“苹果公司新发布的手机”的信息被切分成“苹果公司”和“新发布的手机”两个chunk,单独检索“苹果公司”时,可能返回大量无关的结果。
  • Chunk太大: 虽然包含了更多的上下文,但会增加向量的计算成本和存储成本。同时,如果一个chunk内包含多个主题,可能会导致检索时返回与用户问题不太相关的部分。
  • Embedding模型限制:大部分embedding模型限制输入在几个K token左右,比如Gemini GenAI是输入上限2K,输出768维,OpenAI输入是8k,输出1536维

如何选择合适的Chunk大小?

这是一个需要根据实际播客内容和模型能力进行实验和调整的过程。一些可以参考的策略:

  • 基于句子或段落切分: 这是比较常用的方法,可以保证chunk的语义完整性。
  • 固定大小切分并加上重叠: 将文本按照固定token数量切分,并在相邻的chunk之间添加一定的重叠部分,以保留上下文信息。例如,一个chunk包含100个token,重叠20个token,那么下一个chunk从第81个token开始。
  • 利用语义切分工具: 一些工具可以根据语义相似性来切分文本,使得chunk内部的语义更加连贯。

在我们的实践中,我们尝试了不同的chunk大小,并结合向量检索的效果进行评估。 出于简单的考虑我们选择了固定大小切分并加上重叠。参数是2000个token一个chunk,重叠是200个token,通过tiktoken的包进行本地的计算(因为不知道embedding模型的tokenzier配置,所以这里只是近似)

小结

这篇博文我们深入探讨了播客RAG系统搭建过程中的一些关键技术点和挑战,包括增量更新、大模型转录的重复问题、中文Embedding模型的选择以及chunk大小的权衡。虽然已经有了大模型的加持可以很快编写核心骨架代码(大概降低了一半的时间),但是需求的不断迭代和看到结果后目标不停的调整,还是有相当大量的人为介入。编程门槛的降低,可以让非专业人士和专业人士摆脱一些低级的信息查找,把时间投入更有效率的地方。

后续我会整理一下代码之后发布开源(现在大部分都在notebook里)。

数据库操作系统

今天在推上看到一篇论文推荐,觉得内容很有意思,于是马上下来看。

    

首先文章的作者来自于顶级高校和企业,另外数据库大牛图灵奖获得者Stonebraker(这个名字也太像石破天了)也名列其中。大牛当年怒喷MapReduce引发的论战还记忆犹新。如果说MapReduce是操作系统界入侵数据库界,那这篇文章则可以看成数据库界抄操作系统的后路。

文章链接:https://vldb.org/pvldb/vol15/p21-skiadopoulos.pdf

万物皆表

UNIX时代发明的“Everything is a file”的抽象哲学(并得到Linux的发扬光大)仍被奉为圭臬,但本文则直接挑战这一思想,认为它已经落后于时代。本文一开始列举了诸多计算的趋势——大规模、云、并行计算、异构硬件、新编程模型(例如Serverless)和数据监管等等。针对上面这些问题,本文认为虽然有不少修修补补的方案,但是时候把思路转向更高的层次——本质上是大数据问题,应该用大数据的思路来寻找答案。作者们认为“Everything is a table”就是正确的方向。更具体的说,则是”Everything is a distributed table”,从底层支持分布式和数据库。

顺着万物皆表的思路,很多复杂的功能可以很容易通过数据库实现。比如调度器,可以用两张表分别表示任务队列和工作节点。剩下的工作就是通过存储过程原子地操作这两张表(数据库事务保证了一致性),实现各种调度方式,例如负载均衡、本地优先等等。

第二个例子是IPC。通过消息信箱实现分布式IPC早就不是什么新鲜事,比如Actor模式的编程就是通过给信箱的收发进行通信并解耦消息的收发双方。而数据库可以轻松地实现分布式消息队列。

第三个例子是文件系统。目录项和Inode都分别建表,文件还能分为集中存放(一个shard,并发度高)和全局散布(所有shard以求吞吐量最大化)两种模式。类似对象存储,目录树成为逻辑概念而非物理概念(存放的都是全路径)。当中还举了一个统计目录下文件大小的例子,数据库可以通过SQL的聚合轻松完成,而现代文件系统因为没有这个标准操作所以只能通过一个98行代码的程序完成并且性能差一大截。虽然这个比较并不公平,但数据库强大的功能也可见一斑。我不由得想起了当年Longhorn项目里的WinFS(虽然概念基本不相关),怪不得微软也尝试了多次想把数据库引入用户文件系统。

实现路径

这个研究项目也有实打实的路线图,并且看上去还比较靠谱。毕竟现代操作系统如此复杂,几十年的积累,在底层引入这么大的变化,工程量绝非一般人可以想象。而分布式数据库又是一个大坑。分层替换自然是可行的选择。

首先新的操作系统(称为DBOS)如下图划分为4个层次。

  • 第4层即用户层类似现代操作系统的用户态,在这个层次DBOS仅支持那些分布式应用——这也是本文划定的范围,DBOS并未打算取代现有操作系统的所有领域,比如桌面、移动,而是聚焦在分布式服务器范畴。当然现有的程序肯定也不能直接跑,而是要经过一定的改写,把程序变成由小型无状态任务组成的DAG(有向无环图)。类似Spark这种程序比较符合这种范式。
  • 第3层类似系统调用层。所有的这些服务需要通过分布式数据库实现,而上一节讲了通过数据库怎么实现文件系统、调度器、IPC这些重要的接口或者服务。
  • 第2层即DBOS的核心——分布式数据库。
  • 第1层设计为微服务形式,处理底层硬件的中断事件、节点间通信等等。注意这一层计划放弃某些复杂的管理机制,比如虚拟内存管理(其实现在有一些跑Spark或者k8s应用的服务器已经主动关闭了swap)

类似房子的演化,整个路线图分为3阶段:

  • 草:在第2层使用现有的分布式数据库(VoltDB)基础上,对第3层实现进行概念验证,并编写的第4层应用示例进行性能测试。这个阶段工作已经接近完成并在下一部分给出了一些结果。
  • 木:在Linux集群上(第1层)运行真正的由执行图组成的用户程序,并将部分第3层系统功能替换成系统功能。这一阶段的目的是保证操作系统可以稳定运行在SQL之上。这也是这个项目的目前阶段。
  • 砖:这一阶段尚不是很明朗,亟待木阶段的结果和可以获得的资源来确定具体方案。总体上来说,需要替换掉第1层的实现,并且第3层基本由分布式数据库服务。第2层的分布式数据库如果重写工作量太大。

(不知道以后会不会有钢筋混凝土)

性能为王

学过操作系统课的都知道当年的微内核和宏内核之争。即便微内核的设计多么优雅,计划多么雄心勃勃(正如这个DBOS),性能达不到需求,便只能停留在研究上无法走入工业界。这也是DBOS面对的最大质疑。DBOS-草阶段也主要是为了尽量平息这个争议。

调度器

调度器的测试展示了在分布式环境下单纯任务调度的延迟可以在1M吞吐量下达到200us以内。对于CPU级别的任务调度当然这算不上什么,但是如果考虑调度的目标是平均延迟在100ms的serverless function,这个成绩也足够了。

IPC

IPC的测试对比了单纯的TCP/IP和gRPC。后者是目前应用最广泛的RPC协议。相比gRPC,DBOS的ping-pong测试(网络版的echo)性能较差,但还在同一数量级上。

而在小消息大批次的ping-pong测试(一次性发送20组消息)以及多播测试(一个发送者多个接受者)中,DBOS略优于gRPC。

由于目前VoltDB尚不支持触发器,因此在收件端只能采用性能较低的忙等待轮询。

文件系统

文件系统方面做了两组测试,分别是在本地对比ext4,和集群环境里对比LustreFS。不出意外,单个文件的读取ext4绝对占优,多个文件的读取由于ext4需要多个系统调用因此差距缩小了。写入则是DBOS的长处,因为没有全局锁。文件创建/删除方面,DBOS的优势在于使用了全路径。

和集群文件系统的对比DBOS则在读取上获得得了明显的优势。

小结

DBOS构建的是原生支持分布式和并行计算的操作系统,运行在计算中心里,并无意取代大家所熟悉的Linux/Windows/Mac。可以把DBOS想象成为运行serverless应用、Spark任务的计算平台。在这个平台上编写分布式应用程序将大大简化,并且所有操作都可以溯源(想象一下所有读写都有操作记录并可以回放)。即便如此,这个项目构想的前景依旧非常宏大,即使取得一小部分成功也会对业界产生重大影响。也让我们拭目以待期待项目后续发展。

(最新的进度报告也发表在CIDR2022上:http://cidrdb.org/cidr2022/papers/p26-li.pdf

另外知乎上还有一篇论文解读

C++随记(2)

很简单概念的复习,对构造函数、拷贝构造函数和赋值函数:

  1 #include <stdio.h>

  2                           

  3 class Bar

  4 {

  5   public:

  6     Bar() {printf("ctor\n");}

  7     Bar(Bar& b) {printf("copy ctor\n");}

  8     Bar& operator = (const Bar & b) {printf("assignment =\n"); return *this;}

  9 };

 10 

 

 11 void foo(Bar b)

 12 {

 13 }

 14 

 15 int main()

 16 {   

 17     printf("Ctoring bar1\n");

 18     Bar bar1;

 19     printf("Ctoring bar2\n");

 20     Bar bar2 = bar1;

 21     printf("Ctoring bar3\n");

 22     Bar bar3(bar1);

 23     printf("Assigning bar3\n");

 24     bar3 = bar2;

 25     printf("Pass by value bar3\n");

 26     foo(bar3);

 27     try

 28     {

 29         try 

 30         {   

 31             printf("Throwing bar3\n");

 32             throw bar3;

 33         }   

 34         catch (Bar& bar)

 35         {   

 36             printf("Rethrow bar3\n");

 37             throw;

 38         }

 39     }

 40     catch (…)

 41     {

 42     }

 43 }

       

 
输出结果为,特别注意拷贝构造函数的几种调用方式,特别是最后的异常处理,强制pass by value,即便声明了形参为引用传递。
Ctoring bar1
ctor
Ctoring bar2
copy ctor
Ctoring bar3
copy ctor
Assigning bar3
assignment =
Pass by value bar3
copy ctor
Throwing bar3
copy ctor
Rethrow bar3
 
p.s. OSX终端的拷贝功能居然包括控制台背景和颜色。

Resovling AM_ICONV undefined error when building osxfuse

I got this issue when building osxfuse code:

 
wum@osxfuse$ ./build.sh -t lib
OSXFUSEBuildTool()            : supported platforms: 10.7 10.8
OSXFUSEBuildTool(lib)         : initiating Universal build for 10.7
OSXFUSEBuildTool(lib)         : configuring library source
Running libtoolize…
Running autoreconf…
configure.in:82: warning: macro `AM_ICONV' not found in library
glibtoolize: putting auxiliary files in `.'.
glibtoolize: copying file `./ltmain.sh'
glibtoolize: Consider adding `AC_CONFIG_MACRO_DIR([m4])' to configure.in and
glibtoolize: rerunning glibtoolize, to keep the correct libtool macros in-tree.
glibtoolize: Consider adding `-I m4' to ACLOCAL_AMFLAGS in Makefile.am.
configure.in:82: warning: macro `AM_ICONV' not found in library
configure.in:82: error: possibly undefined macro: AM_ICONV
      If this token and others are legitimate, please use m4_pattern_allow.
      See the Autoconf documentation.
autoreconf: /usr/bin/autoconf failed with exit status: 1
Linking kernel header file…
To compile run './configure', and then 'make'.
configure: error: cannot find install-sh or install.sh in "." "./.." "./../.."
OSXFUSEBuildTool(lib) failed: cannot configure OSXFUSE library source for compilation.
 
I soon googled and find that I was short of the get text library. However installing the library with homebrew didn't help. I try other workarounds but they didn't appear to work.
 
The major problem is that AM_ICONV (used in some automate script) is defined in iconv.m4
 
Soon I realized if there's an issue in the include path. autoconf/glibtoolize is searching the m4 file in /usr/share/aclocal, but gettext's m4 file was installed to /opt/local/share/aclocal/ by my homebrew. I copied all the m4 files from /opt/local/share/aclocal/ to /usr/share/aclocal, and everything was resolved…
 

Xcode中调整控件叠放顺序

Nib可视化编辑器的调整很简单,不需要去点控件然后调整属性(属性里也没有index),只要在左边的Object列表里调整即可,需要浮在上面的控件往下拖即可。
另外一个方法是针对代码手工添加view的,上接口即可:
insertSubview:atIndex: See Also
– addSubview: – insertSubview:aboveSubview:
– insertSubview:belowSubview:
– exchangeSubviewAtIndex:withSubviewAtIndex:

LLVM折腾记(2)

今天主要折腾建立新的编译环境把Release版本的LLVM给编起来,主要是体力活。另外就是学到了一个可以link目录的好办法——mount -bind,这样可以节省很多空间。毕竟我只是想替换一个so文件(libstdc++.so.3.0.6).
新编译环境建好以后很快把Release版本的clang/llvm弄出来了。实验了一次编一个component的代码,效果很不错。GCC需要46秒完成的编译用llvm只需要35秒左右就可以完成,提高了将近四分之一。而在代码大小方面,具体数字不太记得了,不过缩小了估计也有三分之一,很惊人。之后的链接也没出现问题。不过忘记加载image看看这样的代码是否工作了。
下一天的主要工作就是用llvm编译全体代码,找看看有哪些不兼容的地方,顺便做个编译时间和代码体积的测评。

每周技术分享 -1 screen

总觉得应该找到一个方式把一些技术方面的东西记录下来,想不到什么特别的方式,就暂且放blog里把。
这是开篇,虽然加了每周这个限定,但也不一定每周都能更新,算是一个期望吧。内容可长可短。
上班一年来,我现在每天离不开,以前却不知道的工具非screen莫属了。对于不在本地编写编译代码的人而言,肯定是会需要很多终端窗口的,一个写代码,一个查代码,一个编译代码是跑不掉的。另外,代码还有很多branch,还有需要dump调试窗口等等,一个占用一个windows窗口,不仅太占空间,就是一个个打开也很麻烦。一开始打算用putty manager,但用了用觉得不太顺手。后来同事推荐了大名鼎鼎的screen实现上面的功能。
screen也算是一个老牌程序了,大部分linux服务器上应该默认都有的。screen等于在服务器端管理了终端窗口,这带来另外一个好处是即使putty断线了(比如关机、断网),服务器的session也不会终端,只需要重新attach上去就可以了,省去了很多麻烦。而各个终端也支持自己命名,切换也有各种快速切换方式。另外外观也可以通过自定义.screenrc文件来配置。本来一个服务器我最多开3-4个终端,现在上了screen,我经常在服务器上上15+的终端,而遇到需要重启关机的时候,直接把putty关闭,看都不看,因为我知道服务器端保留了所有的终端信息。除非碰到服务器重启等特殊情况,这些终端我基本都一直放着,这样一到公司就可以很快进入工作。
另外screen还提供了服务器终端共享的功能,具体使用可以看screen的manual。这应该算是终端界的桌面共享吧?这个功能我倒是没有用过,有次我mentor在给美国的同事解释代码的时候,一边就着电话,一边就着screen共享session,挺实用的。

通过weather.com.cn获取全国天气数据

获得天气数据:
访问http://m.weather.com.cn/data/101020100.html,其中1010200100是城市的id(上海),返回JSON格式的天气数据,示例如下:
{“weatherinfo”:{“city”:”上海”,”city_en”:”shanghai”,”date_y”:”2009年12月24日”,”date”:”十一月初九”,”week”:”星期四”, “fchh”:”08″,”cityid”:”101020100″,”temp1″:”14℃~6℃”,”temp2″:”9℃~3℃”,”temp3″:”6℃~2℃”, “temp4″:”5℃~1℃”,”temp5″:”7℃~4℃”,”tempF1″:”57.2℉~42.8℉”,”tempF2″:”48.2℉~37.4℉”,”tempF3″:”42.8℉~35.6℉”,”tempF4″:”41℉~33.8℉”,”tempF5″:”44.6℉~39.2℉”,”weather1″:”多云转小雨”,”weather2″:”小雨转多云”,”weather3″:”多云转小雨”,”weather4″:”阴转多云”,”weather5″:”多云”,”img1″:”1″,”img2″:”7″,”img3″:”7″,”img4″:”1″,”img5″:”1″,”img6″:”7″,”img7″:”2″,”img8″:”1″,”img9″:”1″,”img10″:”99″,”img_single”:”1″,”img_title1″:”多云”,”img_title2″:”小雨”,”img_title3″:”小雨”,”img_title4″:”多云”,”img_title5″:”多云”,”img_title6″:”小雨”,”img_title7″:”阴”,”img_title8″:”多云”,”img_title9″:”多云”,”img_title10″:”多云”,”img_title_single”:”多云”,”wind1″:”东北风转北风3-4级”,”wind2″:”北风4-5级”,”wind3″:”北风转东北风4-5级”,”wind4″:”东北风4-5级转北风3-4级”,”wind5″:”西南风3-4级”,”fl1″:”3-4级”,”fl2″:”4-5级”,”fl3″:”4-5级”,”fl4″:”4-5级转3-4级”,”fl5″:”3-4级”,”index”:”舒适”,”index_d”:”建议着薄型套装或牛仔衫裤等春秋过渡装。年老体弱者宜着套装、夹克衫等。”,”index48″:”凉”,”index48_d”:”天气凉,建议着厚外套加毛衣等春秋服装。年老体弱者宜着大衣、呢外套加羊毛衫。”,”index_uv”:”最弱”,”index48_uv”:”最弱”,”index_xc”:”不宜”,”index_tr”:”很适宜”,”index_co”:”较舒适”}}
城市id获取方式(一次性工作):
1. 访问http://m.weather.com.cn/data5/city.xml?level=0,(后面level参数可省略)得到一级列表(省、直辖市、自治区),结果用逗号隔开,id和城市名称使用竖线“|”隔开;结果示例如下:

01|北京,02|上海,03|天津,04|重庆,05|黑龙江,06|吉林,07|辽宁,08|内蒙古,09|河北,10|山西,11|陕西,12|山东,13|新疆,14|西藏,15|青海,16|甘肃,17|宁夏…(以下省略)

2. 访问http://m.weather.com.cn/data5/city02.xml?level=1,(后面level参数可省略)得到二级列表。其中02是一级省市的id,结果格式和上一层相同,示例如下(上海和黑龙江):
0201|上海
0501|哈尔滨,0502|齐齐哈尔,0503|牡丹江,0504|佳木斯,0505|绥化,0506|黑河,0507|大兴安岭,0508|伊春,0509|大庆,0510|七台河,0511|鸡西,0512|鹤岗,0513|双鸭山

3. 访问http://m.weather.com.cn/data5/city0201.xml?level=2,(后面level参数可省略)得到三级列表。0201是地级市的id,示例如下(上海):

020101|上海,020102|闵行,020103|宝山,020104|嘉定,020105|南汇,020106|金山,020107|青浦,020108|松江,020109|奉贤,020110|崇明,020111|徐家汇,020112|浦东

4. 访问http://m.weather.com.cn/data5/city020101.xml?level=3,(后面level参数可省略)得到最后一级的id,020101是区域的id,示例如下(上海市区):
020101|101020100
后面的数字就是获得天气数据需要的城市id,以http://m.weather.com.cn/data/{id}.html格式访问即可得出天气结果。
参考:
chrome天气插件:http://code.google.com/p/chinaweather/,使用Javascript编写

百度在线笔试

上上周百度又让我参加了一轮在线笔试。今天忽然在桌面上看到于是就贴出来。
第一部分、算法与程序设计
1.在一棵一般的二叉树中找到指定的元素,如果有重复出现的元素,要求元素为深度最深的任何一个。指定元素找不到时返回EMPTY_NODE,请用C语言实现,相关数据结构与函数声明如下:
struct Node
{
int iValue;
int id;
Node *pLeft;
Node *pRight;
};
const Node EMPTY_NODE = {0, 0, NULL, NULL};
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点,wanted为指定元素的iValue
2.一个单词字典库,单词个数约为10万,每个单词长度不超过16,单词都是由小写字母组成,同时给出16个小写字母,请设计一种高效算法来找到用这些给出字母拼出一个字典中最大长度的单词。给出的16个字母每个字母最多使用一次,也可以不使用。存在多解的时候给出任意一个最优答案就行。
例如:给出adeenrstuvxyzuki可以拼出adventures
请详细描述你的算法思路(如需要,可给出代码\伪代码来辅助描述),并分析其时间复杂度。最后请分析下你的算法以及数据结构的优缺点,存在哪些可改进的地方。
第二部分、系统设计题
1.       有200亿条数据,每条数据的大小在1K~1M不等,每条数据有一个唯一的u_int64的id。
请设计一个读取数据系统,能根据id获取数据。要求:
A.        内存有限制,16G
B.        尽可能利用内存资源
C.        尽可能高效的获取数据
D.        可以利用磁盘,磁盘容量不受限制
2.       C2C网站的商品子系统,包括的关系数据有 分类、属性、商品。
一个商品只能属于一个分类,不同的分类有不同的属性(多个),每个属性有多个候选属性值,其中分类、属性、属性值的更新频率较低。
一个商品的属性,是所属分类的属性,属性值是候选属性值中的一个或多个。
例如:
分类:衣服
属性:尺寸、颜色
尺寸的候选属性值:S/M/L/XL/XXL/XXXL
颜色的候选属性值:黑/白/红/黄/蓝
商品:衣服A,尺寸S,颜色黑
另外,商品还有卖家、价格等其它信息
请设计商品子系统的存储结构或数据库结构。要求:
A.        能够正确维护分类、属性、商品之间的关系数据
B.        尽量减少冗余
C.        考虑数据的增、删、改、查操作,效率尽可能高
D.        能够按照卖家查询出其发布的所有商品
==============问题和解答的分割线======================
1111111111111111111111111111111111111111111111111111111111111111111111111111
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点,wanted为指定元素的iValue
{
return findDeepestWithDepth(pRoot, iWanted, 1);
}
Node findDeepestWithDepth(Node *pRoot, int iWanted, int depth)
{
static int maxDepth = 1;
static Node deepestNode = EMPTY_NODE;
if(pRoot != null)
{
Node l = findDeepestWithDepth(pRoot->pLeft, iWanted, depth+1);
Node r = findDeepestWithDepth(pRoot->pRight, iWanted, depth+1);
if(isEmpty(l) && isEmpty(r))
{
if(maxDepth < depth)
{
maxDepth = depth;
node = *pRoot;
return *pRoot;
}
else
{
return deepestNode;
}
}
else
{
return deepestNode;
}
}
else
{
return EMPTY_NODE;
}
}
bool isEmpty(Node node)
{
return node.iValue == 0 && node.id == 0 && node.pLeft == NULL && node.pRight == NULL;
}
2222222222222222222222222222222222222222222222222222222222222222222222222
1. 对字典中每一个单词进行遍历,计算出每个单词每个字母的个数和单词的长度
2. 针对每个单词里每个字母(a-z)的个数和单词的长度建立索引,类似数据库的一张表,表一共有28个列(加上一个隐含的rowid),包括单词内容(1列),26个字母每个字母的个数(26列)和单词的长度
3. 搜索时,对给定的字符串进行相同的统计,计算出每个字母的个数。根据统计结果去搜索个数小于给定字符串字母的单词的rowid,最多16次搜索,搜索后对结果进行交集(思想类似: select word from words where a <= 1 and b <= 1 and d <= 2 and …)
4. 对最后的交集根据长度,得出最长的单词的rowid,最终得出单词
时间复杂度: 16次搜索,每次为O(log n),最多15次的交集运算,复杂度为O(logn * logn),最后寻找最大值可以忽略,所以时间复杂度为O(logn*logn)
改进:提高索引效率,如联合索引
33333333333333333333333333333333333333333333333333333333333333333333333333
1. 内存中使用二叉搜索树进行索引,每个节点占用16字节(2个指针+1个id),可放10亿个节点,则底层节点有5亿个。底层节点左右为空,8个字节用来表示记录在磁盘的存储位置
2. 磁盘存储分为5亿块,每个块里有40条记录
3. 块分为块头索引和块内容。块头索引按id顺序排列,包括了该块的id,起始位置和长度。块头大小为40*(8+8+4)=800字节
4. 每次通过id访问数据,首先查找二叉搜索树,经过29次内存比较得到索引块,再载入索引块头,使用二分搜索得到内容的起始位置和长度,最终得到内容。一共35次左右内存访问和2次磁盘访问
44444444444444444444444444444444444444444444444444444444444444444444444444444
商品表 product: id, name, seller, price, category
分类表 category: id, name
属性表 attribute: id, name, category_id, type
属性候选值表 attribute_value: id, attribute_id, value
商品属性表 product_value: product_id, attribute_value_id