algorithm blog

Sunday, March 14, 2010

STSC CrossTalk - Computer Science Education: Where Are the Software Engineers of Tomorrow? - Jan 2008

STSC CrossTalk - Computer Science Education: Where Are the Software Engineers of Tomorrow? - Jan 2008

STSC Logo About Us Consulting Services CrossTalk STC Conference Resources
Search


Software Technology Support Center


About CrossTalk

- Mission
- Staff
- Contact Us


About Us

Subscription

- Subscribe Now
- Update
- Cancel
-


Themes Calendar

Author Guidelines

Back Issues

Article Index

Your Comments
Home > CrossTalk Jan 2008 > Article

CrossTalk - The Journal of Defense Software Engineering Jan 2008 Issue

Computer Science Education: Where Are the Software Engineers of Tomorrow?
Dr. Robert B.K. Dewar, AdaCore Inc.
Dr. Edmond Schonberg, AdaCore Inc.

It is our view that Computer Science (CS) education is neglecting basic skills, in particular in the areas of programming and formal methods. We consider that the general adoption of Java as a first programming language is in part responsible for this decline. We examine briefly the set of programming skills that should be part of every software professional’s repertoire.

It is all about programming! Over the last few years we have noticed worrisome trends in CS education. The following represents a summary of those trends:

1. Mathematics requirements in CS programs are shrinking.
2. The development of programming skills in several languages is giving way to cookbook approaches using large libraries and special-purpose packages.
3. The resulting set of skills is insufficient for today’s software industry (in particular for safety and security purposes) and, unfortunately, matches well what the outsourcing industry can offer. We are training easily replaceable professionals.

These trends are visible in the latest curriculum recommendations from the Association for Computing Machinery (ACM). Curriculum 2005 does not mention mathematical prerequisites at all, and it mentions only one course in the theory of programming languages [1].

We have seen these developments from both sides: As faculty members at New York University for decades, we have regretted the introduction of Java as a first language of instruction for most computer science majors. We have seen how this choice has weakened the formation of our students, as reflected in their performance in systems and architecture courses. As founders of a company that specializes in Ada programming tools for mission-critical systems, we find it harder to recruit qualified applicants who have the right foundational skills. We want to advocate a more rigorous formation, in which formal methods are introduced early on, and programming languages play a central role in CS education.
Formal Methods and Software Construction

Formal techniques for proving the correctness of programs were an extremely active subject of research 20 years ago. However, the methods (and the hardware) of the time prevented these techniques from becoming widespread, and as a result they are more or less ignored by most CS programs. This is unfortunate because the techniques have evolved to the point that they can be used in large-scale systems and can contribute substantially to the reliability of these systems. A case in point is the use of SPARK in the re-engineering of the ground-based air traffic control system in the United Kingdom (see a description of iFACTS – Interim Future Area Control Tools Support, at ). SPARK is a subset of Ada augmented with assertions that allow the designer to prove important properties of a program: termination, absence of run-time exceptions, finite memory usage, etc. [2]. It is obvious that this kind of design and analysis methodology (dubbed Correctness by Construction) will add substantially to the reliability of a system whose design has involved SPARK from the beginning. However, PRAXIS, the company that developed SPARK and which is designing iFACTS, finds it hard to recruit people with the required mathematical competence (and this is present even in the United Kingdom, where formal methods are more widely taught and used than in the United States).

Another formal approach to which CS students need exposure is model checking and linear temporal logic for the design of concurrent systems. For a modern discussion of the topic, which is central to mission-critical software, see [3].

Another area of computer science which we find neglected is the study of floating-point computations. At New York University, a course in numerical methods and floating-point computing used to be required, but this requirement was dropped many years ago, and now very few students take this course. The topic is vital to all scientific and engineering software and is semantically delicate. One would imagine that it would be a required part of all courses in scientific computing, but these often take MatLab to be the universal programming tool and ignore the topic altogether.
The Pitfalls of Java as a First Programming Language

Because of its popularity in the context of Web applications and the ease with which beginners can produce graphical programs, Java has become the most widely used language in introductory programming courses. We consider this to be a misguided attempt to make programming more fun, perhaps in reaction to the drop in CS enrollments that followed the dot-com bust. What we observed at New York University is that the Java programming courses did not prepare our students for the first course in systems, much less for more advanced ones. Students found it hard to write programs that did not have a graphic interface, had no feeling for the relationship between the source program and what the hardware would actually do, and (most damaging) did not understand the semantics of pointers at all, which made the use of C in systems programming very challenging.

Let us propose the following principle: The irresistible beauty of programming consists in the reduction of complex formal processes to a very small set of primitive operations. Java, instead of exposing this beauty, encourages the programmer to approach problem-solving like a plumber in a hardware store: by rummaging through a multitude of drawers (i.e. packages) we will end up finding some gadget (i.e. class) that does roughly what we want. How it does it is not interesting! The result is a student who knows how to put a simple program together, but does not know how to program. A further pitfall of the early use of Java libraries and frameworks is that it is impossible for the student to develop a sense of the run-time cost of what is written because it is extremely hard to know what any method call will eventually execute. A lucid analysis of the problem is presented in [4].

We are seeing some backlash to this approach. For example, Bjarne Stroustrup reports from Texas A & M University that the industry is showing increasing unhappiness with the results of this approach. Specifically, he notes the following:

I have had a lot of complaints about that [the use of Java as a first programming language] from industry, specifically from AT&T, IBM, Intel, Bloomberg, NI, Microsoft, Lockheed-Martin, and more. [5]

He noted in a private discussion on this topic, reporting the following:

It [Texas A&M] did [teach Java as the first language]. Then I started teaching C++ to the electrical engineers and when the EE students started to out-program the CS students, the CS department switched to C++. [5]

It will be interesting to see how many departments follow this trend. At AdaCore, we are certainly aware of many universities that have adopted Ada as a first language because of similar concerns.
A Real Programmer Can Write in Any Language (C, Java, Lisp, Ada)

Software professionals of a certain age will remember the slogan of old-timers from two generations ago when structured programming became the rage: Real programmers can write Fortran in any language. The slogan is a reminder of how thinking habits of programmers are influenced by the first language they learn and how hard it is to shake these habits if you do all your programming in a single language. Conversely, we want to say that a competent programmer is comfortable with a number of different languages and that the programmer must be able to use the mental tools favored by one of them, even when programming in another. For example, the user of an imperative language such as Ada or C++ must be able to write in a functional style, acquired through practice with Lisp and ML1, when manipulating recursive structures. This is one indication of the importance of learning in-depth a number of different programming languages. What follows summarizes what we think are the critical contributions that well-established languages make to the mental tool-set of real programmers. For example, a real programmer should be able to program inheritance and dynamic dispatching in C, information hiding in Lisp, tree manipulation libraries in Ada, and garbage collection in anything but Java. The study of a wide variety of languages is, thus, indispensable to the well-rounded programmer.
Why C Matters

C is the low-level language that everyone must know. It can be seen as a portable assembly language, and as such it exposes the underlying machine and forces the student to understand clearly the relationship between software and hardware. Performance analysis is more straightforward, because the cost of every software statement is clear. Finally, compilers (GCC for example) make it easy to examine the generated assembly code, which is an excellent tool for understanding machine language and architecture.
Why C++ Matters

C++ brings to C the fundamental concepts of modern software engineering: encapsulation with classes and namespaces, information hiding through protected and private data and operations, programming by extension through virtual methods and derived classes, etc. C++ also pushes storage management as far as it can go without full-blown garbage collection, with constructors and destructors.
Why Lisp Matters

Every programmer must be comfortable with functional programming and with the important notion of referential transparency. Even though most programmers find imperative programming more intuitive, they must recognize that in many contexts that a functional, stateless style is clear, natural, easy to understand, and efficient to boot.

An additional benefit of the practice of Lisp is that the program is written in what amounts to abstract syntax, namely the internal representation that most compilers use between parsing and code generation. Knowing Lisp is thus an excellent preparation for any software work that involves language processing.

Finally, Lisp (at least in its lean Scheme incarnation) is amenable to a very compact self-definition. Seeing a complete Lisp interpreter written in Lisp is an intellectual revelation that all computer scientists should experience.
Why Java Matters

Despite our comments on Java as a first or only language, we think that Java has an important role to play in CS instruction. We will mention only two aspects of the language that must be part of the real programmer’s skill set:

1. An understanding of concurrent programming (for which threads provide a basic low-level model).
2. Reflection, namely the understanding that a program can be instrumented to examine its own state and to determine its own behavior in a dynamically changing environment.

Why Ada Matters

Ada is the language of software engineering par excellence. Even when it is not the language of instruction in programming courses, it is the language chosen to teach courses in software engineering. This is because the notions of strong typing, encapsulation, information hiding, concurrency, generic programming, inheritance, and so on, are embodied in specific features of the language. From our experience and that of our customers, we can say that a real programmer writes Ada in any language. For example, an Ada programmer accustomed to Ada’s package model, which strongly separates specification from implementation, will tend to write C in a style where well-commented header files act in somewhat the same way as package specs in Ada. The programmer will include bounds checking and consistency checks when passing mutable structures between subprograms to mimic the strong-typing checks that Ada mandates [6]. She will organize concurrent programs into tasks and protected objects, with well-defined synchronization and communication mechanisms.

The concurrency features of Ada are particularly important in our age of multi-core architectures. We find it surprising that these architectures should be presented as a novel challenge to software design when Ada had well-designed mechanisms for writing safe, concurrent software 30 years ago.
Programming Languages Are Not the Whole Story

A well-rounded CS curriculum will include an advanced course in programming languages that covers a wide variety of languages, chosen to broaden the understanding of the programming process, rather than to build a résumé in perceived hot languages. We are somewhat dismayed to see the popularity of scripting languages in introductory programming courses. Such languages (Javascript, PHP, Atlas) are indeed popular tools of today for Web applications. Such languages have all the pedagogical defaults that we ascribe to Java and provide no opportunity to learn algorithms and performance analysis. Their absence of strong typing leads to a trial-and-error programming style and prevents students from acquiring the discipline of separating design of interfaces from specifications.

However, teaching the right languages alone is not enough. Students need to be exposed to the tools to construct large-scale reliable programs, as we discussed at the start of this article. Topics of relevance are studying formal specification methods and formal proof methodologies, as well as gaining an understanding of how high-reliability code is certified in the real world. When you step into a plane, you are putting your life in the hands of software which had better be totally reliable. As a computer scientist, you should have some knowledge of how this level of reliability is achieved. In this day and age, the fear of terrorist cyber attacks have given a new urgency to the building of software that is not only bug free, but is also immune from malicious attack. Such high-security software relies even more extensively on formal methodologies, and our students need to be prepared for this new world.
References

1. Joint Taskforce for Computing Curricula. “Computing Curricula 2005: The Overview Report.” ACM/AIS/ IEEE, 2005 .
2. Barnes, John. High Integrity Ada: The Spark Approach. Addison-Wesley, 2003.
3. Ben-Ari, M. Principles of Concurrent and Distributed Programming. 2nd ed. Addison-Wesley, 2006.
4. Mitchell, Nick, Gary Sevitsky, and Harini Srinivasan. “The Diary of a Datum: An Approach to Analyzing Runtime Complexity in Framework-Based Applications.” Workshop on Library-Centric Software Design, Object-Oriented Programming, Systems, Languages, and Applications, San Diego, CA, 2005.
5. Stroustrup, Bjarne. Private communication. Aug. 2007.
6. Holzmann Gerard J. “The Power of Ten – Rules for Developing Safety Critical Code.” IEEE Computer June 2006: 93-95.

Note

1. Several programming language and system names have evolved from acronyms whose formal spellings are no longer considered applicable to the current names for which they are readily known. ML, Lisp, GCC, PHP, and SPARK fall under this category.

About the Authors
Dr. Robert B.K. Dewar

Robert B.K. Dewar, Ph.D., is president of AdaCore and a professor emeritus of computer science at New York University. He has been involved in the design and implementation of Ada since 1980 as a distinguished reviewer, a member of the Ada Rapporteur group, and the chief architect of Gnu Ada Translator. He was a member of the Algol68 committee and is the designer and implementor of Spitbol. Dewar lectures widely on programming languages, software methodologies, safety and security, and on intellectual property rights. He has a doctorate in chemistry from the University of Chicago.

AdaCore
104 Fifth AVE 15th FL
New York, NY 10011
Phone: (212) 620-7300 ext. 100
Fax: (212) 807-0162
E-mail: dewar@adacore.com

Dr. Edmond Schonberg

Edmond Schonberg, Ph.D., is vice-president of AdaCore and a professor emeritus of computer science at New York University. He has been involved in the implementation of Ada since 1981. With Robert Dewar and other collaborators, he created the first validated implementation of Ada83, the first prototype compiler for Ada9X, and the first full implementation of Ada2005. Schonberg has a doctorate in physics from the University of Chicago.

AdaCore
104 Fifth AVE 15th FL
New York, NY 10011
E-mail: schonberg@adacore.com


USAF Logo

Privacy and Security Notice · External Links Disclaimer · Site Map · Contact Us


Please E-mail or call 801-775-5555 (DSN 775-5555) if you have any questions regarding your CrossTalk subscription or for additional STSC information.

Webmaster: 517th SMXS/MDEA, 801-777-0857 (DSN 777-0857), E-mail

STSC Parent Organizations: 309SMXG Ogden Air Logistics Center, Hill AFB


Consulting Svcs
CrossTalk
Conference
Customers
Contact Us
Site Map
CMMI
SW Estimation
Proc Improvement
Project Mgmt
Configuration Mgmt
Sys Eng & Development
SW Measurement
SW Quality Engineering
Tech Adoption Svcs
About CrossTalk
Current Issue
Subscription
Theme Calendar
Author Guidelines
Back Issues
Article Index
Your Comments
Seminars
Events
Technical Docs
Web Sites
FAQ
Help Desk

Wednesday, January 27, 2010

Amazon Interview Question: Design an OO parking lot - Stack Overflow

Amazon Interview Question: Design an OO parking lot - Stack Overflow



Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.

Thanks!
object-oriented-design interview-questions
flag

edited Apr 19 at 6:28
ojblass
4,823●8●26

asked Apr 19 at 6:07
burnt1ce
1,124●11

54% accept rate

2

Did you leap up and exclaim "what does this have to do with books?" and storm out? – JP Alioto Apr 19 at 6:39

I got asked that by a guy who went on to another situation. When I used a nearly textbook Gang of Four pattern appropriately, he said "At least you know polymorphism." I was then thanked for coming, and told they'd let me know. I wasn't impressed. – David Thornley May 7 at 17:18
4 Answers
oldest newest votes
vote up 9 vote down check


Here is a quick start to get the gears turning...

ParkingLot is a class.

ParkingSpace is a class.

ParkingSpace has an Entrance.

Entrance has a location or more specifically, distance from Entrance.

ParkingLotSign is a class.

ParkingLot has a ParkingLotSign.

ParkingLot has a finite number of ParkingSpaces.

HandicappedParkingSpace is a subclass of ParkingSpace.

RegularParkingSpace is a subclass of ParkingSpace.

CompactParkingSpace is a subclass of ParkingSpace.

ParkingLot keeps array of ParkingSpaces, and a separate array of vacant ParkingSpaces in order of distance from its Entrance.

ParkingLotSign can be told to display "full", or "empty", or "blank/normal/partially occupied" by calling .Full(), .Empty() or .Normal()

Parker is a class.

Parker can Park().

Parker can Unpark().

Valet is a subclass of Parker that can call ParkingLot.FindVacantSpaceNearestEntrance(), which returns a ParkingSpace.

Parker has a ParkingSpace.

Parker can call ParkingSpace.Take() and ParkingSpace.Vacate().

Parker calls Entrance.Entering() and Entrance.Exiting() and ParkingSpace notifies ParkingLot when it is taken or vacated so that ParkingLot can determine if it is full or not. If it is newly full or newly empty or newly not full or empty, it should change the ParkingLotSign.Full() or ParkingLotSign.Empty() or ParkingLotSign.Normal().

HandicappedParker could be a subclass of Parker and CompactParker a subclass of Parker and RegularParker a subclass of Parker. (might be overkill, actually.)

In this solution, it is possible that Parker should be renamed to be Car.
link|flag

edited Apr 19 at 6:28


answered Apr 19 at 6:22
Christopher Morley
330●1●10

2

Please don't forget car. – ojblass Apr 19 at 6:31
vote up 1 vote down


In an Object Oriented parking lot, there will be no need for attendants because the cars will "know how to park".

Finding a usable car on the lot will be difficult; the most common models will either have all their moving parts exposed as public member variables, or they will be "fully encapsulated" cars with no windows or doors.

The parking spaces in our OO parking lot will not match the size and shape of the cars (an "impediance mismatch" between the spaces and the cars)

License tags on our lot will have a dot between each letter and digit. Handicaped parking will only be available for licenses beginning with "_", and licenses beginning with "m_" will be towed.
link|flag

answered Apr 19 at 6:31
Paul Keister
486●1●7


vote up 0 vote down


you would need a parking lot, that holds a multi-dimensional array (specified in the constructor) of a type "space". The parking lot can keep track of how many spaces are taken via calls to functions that fill and empty spaces.Space can hold an enumerated type that tells what kind of space it is. Space also has a method taken(). for the valet parking, just find the first space thats open and put the car there. You will also need a Car object to put in the space, that holds whether it is a handicapped, compact, or regular vehicle.


class ParkingLot
{
Space[][] spaces;

ParkingLot(wide, long); // constructor

FindOpenSpace(TypeOfCar); // find first open space where type matches
}

enum TypeOfSpace = {compact, handicapped, regular };
enum TypeOfCar = {compact, handicapped, regular };

class Space
{
TypeOfSpace type;
bool empty;
// gets and sets here
// make sure car type
}

class car
{
TypeOfCar type;
}

link|flag

answered Apr 19 at 6:32
Scott M.
1,037●10


vote up 0 vote down


Models don't exist in isolation. The structures you'd define for a simulation of cars entering a car park, an embedded system which guides you to a free space, a car parking billing system or for the automated gates/ticket machines usual in car parks are all different.

Saturday, January 23, 2010

百度分词算法详解 - 上海SEO

百度分词算法详解 - 上海SEO

百度分词算法详解
Chris | 2007-08-21 |

今天无意中读到的,网上转载很多了,不过还是忍不住在转载一番,不过原文就找不到了,读得有点累,但是多少有点启发了,推荐一下。

查询处理以及分词技术

随着搜索经济的崛起,人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业,会根据搜索引擎的知名度以及日流量来选择是否要投放广告等;作为普通网民,会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料;作为技术人员,会把有代表性的搜索引擎作为研究对象。搜索引擎经济的崛起,又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据,以及大量等待去费力挖掘的金矿。

但是,如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎。搜索引擎涉及到许多技术点,比如查询处理,排序算法,页面抓取算法,CACHE机制,ANTI-SPAM等等。这些技术细节,作为商业公司的搜索引擎服务提供商比如百度,GOOGLE等是不会公之于众的。我们可以将现有的搜索引擎看作一个黑盒,通过向黑盒提交输入,判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节。

查询处理与分词是一个中文搜索引擎必不可少的工作,而百度作为一个典型的中文搜索引擎一直强调其“中文处理”方面具有其它搜索引擎所不具有的关键技术和优势。那么我们就来看看百度到底采用了哪些所谓的核心技术。

我们分两个部分来讲述:查询处理/中文分词。

一、查询处理

用户向搜索引擎提交查询,搜索引擎一般在接受到用户查询后要做一些处理,然后在索引数据库里面提取相关的信息。那么百度在接受到用户查询后做了些什么工作呢?

1、假设用户提交了不只一个查询串,比如“信息检索 理论 工具”。那么搜索引擎首先做的是根据分隔符比如空格,标点符号,将查询串分割成若干子查询串,比如上面的查询就会被解析为:<信息检索,理论,工具>三个子字符串;这个道理简单,我们接着往下看。

2、 假设提交的查询有重复的内容,搜索引擎怎么处理呢?比如查询“理论工具理论”,百度是将重复的字符串当作只出现过一次,也就是处理成等价的“理论工具”,而GOOGLE显然是没有进行归并,而是将重复查询子串的权重增大进行处理。那么是如何得出这个结论的呢?我们可以将“理论工具”提交给百度,返回341,000篇文档,大致看看第一页的返回内容。

OK。 继续,我们提交查询“理论工具理论”,在看看返回结果,仍然是那么多返回文档,当然这个不能说明太多问题,那看看第一页返回结果的排序,看出来了吗?顺序完全没有变化,而 GOOGLE 则排序有些变动,这说明百度是将重复的查询归并成一个处理的,而且字符串之间的先后出现顺序基本不予考虑(GOOGLE是考虑了这个顺序关系的)。

3、假设提交的中文查询包含英文单词,搜索引擎是怎么处理的?比如查询”电影BT下载”,百度的方法是将中文字符串中的英文当作一个整体保留,并以此为断点将中文切分开,这样上述的查询就切为<电影,BT,下载>,不论中间的英文是否一个字典里能查到的单词也好,还是随机的字符也好,都会当作一个整体来对待。至于为什么,你用查询“电影dfdfdf下载”看看结果就知道了。当然如果查询中包含数字,也是如此办理。

到目前为止,一切很简单,也很清楚,百度怎么处理用户查询的呢?归纳如下:首先根据分割符号将查询分开,然后看看是否有重复的字符串,如果有,就抛弃多余的,只保留一个,接着判断是否有英文或者数字,如果有的话,把英文或者数字当作一个整体保留并把前后的中文切开。

接着该干什么呢?该考虑分词的问题了。

二、中文分词

首先,讲讲百度的分词时机或者条件问题,是否是个中文字符串百度就拿来切一下呢?非也,要想被百度的分词程序荣幸的切割一下也是要讲条件的,哪能是个字符串就切割啊?你当百度是卖锯条的么?

那么什么样的字符串才满足被切割的条件呢?简单说来,如果字符串只包含小于等于3个中文字符的话,那就保留不动,当字符串长度大于4个中文字符的时候,百度的分词程序才出马大干快上,把这个字符串肢解掉。

怎么证明呢?我们向百度提交“电影下载”,看看返回结果中标为红字的地方,不难看出来,查询已经被切割成<电影,下载>两个单词了,说明分词程序已经开工了,如果是比4个中文字符更长的字符串,那分词程序就更不客气了,一定大卸八块而后快。我们来看看三个字符的情况,提交查询“当然择”,看起来这个查询不伦不类,那是因为我希望看到这个字符串被切分为<当然,择>,返回结果365篇相关页面,翻到最后一页,发现标红的关键字都是” 当然择”连续出现的情况,好像没有切分,但是还不确定,那么再提交人工分好的查询“当然择”看看,返回结果1,090,000篇,基本上可以确定没有进行分词了,当然另外一种解释是:对于三个字符先切分,然后将切分后的结果当作一个短语查询,这样看到的效果和没有切分是相似的。

但是我倾向于判断百度对于少于3个字符的串没有切分,奥卡姆不是说了么“如无必要,勿增实体”,干吗做无用功呢。那么如果没有切分,会有一个随之而来的问题,怎么从索引库里面提取未切分的字符串呢?这牵扯到索引的问题,我觉得百度应该采取了两套索引机制,一种是按照单词索引,一种是按照N-GRAM索引,至于索引的具体问题,以后在详细论述。

下面我们看看百度是采取的何种分词算法,现在分词算法已经算是比较成熟了,有简单的有复杂的,比如正向最大匹配,反向最大匹配,双向最大匹配,语言模型方法,最短路径算法等等,有兴趣的可以用GOOGLE去搜索一下以增加理解。这里就不展开说了。但是要记住一点的是:判断一个分词系统好不好,关键看两点,一个是消除歧义能力;一个是词典未登录词的识别比如人名,地名,机构名等。

那么百度用的是什么方法?我的判断是用双向最大匹配算法。至于怎么推理得出的,让我们一步步来看。当然,这里首先有个假设,百度不会采取比较复杂的算法,因为考虑到速度问题。

我们提交一个查询“毛泽东北京华烟云”,又一个不知所云的查询,尽管不知所云但是自有它的道理,我想看看百度的分词是如何消歧以及是否有词典未登录词的识别的功能,如果是正向最大匹配算法的话,那么输出应该是:”毛泽东/北京/华/烟云”,如果是反向最大匹配算法的话,那么输出应该是:”毛/泽/东北/京华烟云”,我们看看百度的分词结果:”毛泽东/北/京华烟云”,一个很奇怪的输出,跟我们的期望相差较多,但是从中我们可以获得如下信息:百度分词可以识别人名,也可以识别”京华烟云”,这说明有词典未登录词的识别的功能,我们可以假设分词过程分为两个阶段:第一阶段,先查找一个特殊词典,这个词典包含一些人名,部分地名以及一些普通词典没有的新词,这样首先将”毛泽东”解析出来,剩下了字符串”北京华烟云”,而”北/京华烟云”,可以看作是反向最大匹配的分词结果。这样基本说得通。为了证明这一点,我们提交查询”发毛泽东北”,我们期望两种分词结果,一个是正向最大匹配<发毛,泽,东北>,一个是上述假设的结果<发,毛泽东,北>,事实上百度输出是第二种情况,这样基本能确定百度分词采取了至少两个词典,一个是普通词典,一个是专用词典(人名等)。而且是专用词典先切分,然后将剩余的片断交由普通词典来切分。

继续测验,提交查询“古巴比伦理”,如果是正向最大匹 配,那么结果应该是<古巴比伦,理>,如果是反向最大匹配,那么结果应该是 <古巴,比,伦理>,事实上百度的分词结果是<古巴比伦,理>,从这个例子看,好像用了正向最大匹配算法;此外还有一些例子表明好像是使用正向最大匹配的;但是且慢,我们看这个查询“北京华烟云”,正向最大匹配期望的结果是<北京,华,烟云>,而反向最大匹配期望的结果是 <北,京华烟云>,事实上百度输出的是后者,这说明可能采用的反向最大匹配;从这点我们可以猜测百度采用的是双向最大匹配分词算法,如果正向和反向匹配分词结果一致当然好办,直接输出即可;但是如果两者不一致,正向匹配一种结果,反向匹配一种结果,此时该如何是好呢?

从上面两个例子看,在这种情况下,百度采取最短路径方法,也就是切分的片断越少越好,比如<古巴,比,伦理>和<古巴比伦,理>相比选择后者,<北京,华,烟云>和<北,京华烟云>相比选择后者。还有类似的一些例子,这样基本可以解释这些输出结果。

但是仍然遗留的问题是:如果正向反向分词不一致,而且最短路径也相同,那怎么办?输出正向的还是反向的结果?
我们再来看一个例子。提交查询“遥远古古巴比伦”,这个查询被百度切分为<遥远,古古,巴比伦>,说明词典里面有”巴比伦”,但是是否有”古巴比伦”这个词汇不确定,此时看不出是正向切分还是反向切分得出的结果,换查询为“遥远古巴比伦”,此时被切分为“遥远/古巴比伦”,这说明词典里面有”古巴比伦”这个词汇,这说明了“遥远古古巴比伦”是正向最大匹配的结果。那为什么“遥远古古巴比伦”不会被反向切分为”遥/远古/古巴比伦”呢,百度的可能选择是这种情况下选择单字少的那组切分结果。

当然还可以继续追问:如果切分后单字也一样多,那怎么办?最后看一个例子,查询“王强大小:”,百度将其切分为“王/强大/小”,是正向切分的结果,如果是反向的会被切分为“王/强/大小”,这说明有歧义而且单字也相同则选择正向切分结果。

OK,看到这里可能头已经有些晕了,最后总结一下百度的分词算法,当然里面还是有猜测的成分,算法如下:

首先查询专用词典(人名,部分地名等),将专有名称切出,剩下的部分采取双向分词策略,如果两者切分结果相同,说明没有歧义,直接输出分词结果。如果不一致,则输出最短路径的那个结果,如果长度相同,则选择单字词少的那一组切分结果。如果单字也相同,则选择正向分词结果。

百度一直宣传自己在中文处理方面的优势,从上面看,分词算法并无特殊之处,消歧效果并不理想,即使百度采取比上述分词算法复杂些的算法也难以说成是优势,如果说百度有优势的话,唯一的优势就是那个很大的专用词典,这个专用词典登录了人名(比如大长今),称谓(比如老太太),部分地名(比如阿联酋等),估计百度采用学术界公布的比较新的命名实体识别算法从语料库里面不断识别出词典未登录词,逐渐扩充这个专门词典。如果这就是优势的话,那么这个优势能够保持多久就是个很明显的问题。

Spelling Checker拼写检查错误提示(以及拼音提示功能)

拼写检查错误提示是搜索引擎都具备的一个功能,也就是说用户提交查询 给搜索引擎,搜索引擎检查看是否用户输入的拼写有错误,对于中文用户来说一般造成的错误是输入法造成的错误.那么我们就来分析看看百度是 怎么实现这一功能的.

我们分析拼写检查系统关注以下几个问题:

(1)系统如何判断用户的输入是有可能发生错误的查询呢?
(2)如果判断是可能错误的查询输入,如何提示正确的词汇呢?

那么百度是如何做的呢?百度判断用户输入是否错误的标准,我觉得应该是查字典,如果发现字典里面不包含这个词汇,那么很有可能是个错误的输入,此时启动错误提示功能,这个很好判断,因为如果是一个正常词汇的话,百度一般不会有错误提示,而你故意输入一个词典不可能包含的所谓词汇,此时百度一般会提示你正确的检索词汇.

那么百度是怎么提示正确词汇的呢?很明显是通过拼音的方式,比如我输入查询” 制才”,百度提供的提示词汇为: “:制裁 质材纸材”,都是同音字.所以百度必然维持着一个同音词词典,里面保留着同音词信息,比如可能包含着下面这条词条: “ zhi cai à制裁,质材,纸材”,另外还有一 个标注拼音程序,现在能够看到的基本流程是: 用户输入” 制才”,查词典,发现没有这个词汇,OK,启动标注拼音程序,将” 制才”标注为拼音”zhi cai”,然后查找同音词词典,发现同音词” 制裁,质材,纸材”,那么提示用户可能的正确拼写.

整体流程看起来很简单,但是还有一些遗留的小问题,比如是否将词表里面所有同音词都作为用户的提示信息呢?比如某个拼音有10个同音词,是否都输出呢?百度并没有将所有同音词都输出而是选择一定筛选标准,选择其中几个输出.怎么证明这一点?我们看看拼音”liu li”的同音词,紫光输入法提示同音词汇有” 流丽 流离琉璃流利”4个,我们看看百度返回几个,输入”流厉”作为查询,这里是故意输入一个词典不包含的词汇,这样百度的拼写检查才开始工作,百度提示: ” 琉璃刘丽 刘莉 “,这说明什么?说明不是所有同音词都输出,而是选择输出,那么选择的标准是什么?

我能够猜测到的方法是对于用户查询LOG进行统计,提取用户查询次数多的那些同音词输出,如果是这样的话,上面的例子说明用户搜索”琉璃”次数比其它的都要高些,次之是” 刘丽”,再次是” 刘莉”,看来大家都喜欢查询自己或者认识的人的名字.

另外一个小问题:同音词词典包含2字词,3字词,那么是否包含4字词以及更长的词条?是否包含一字词? 这里一字词好回答,不用测试也能知道肯定不包含,因为你输入一个字,谁知道是否是错误的呢?

反正只要是汉字就能在词表里面找到,所以没有判断依据.二字词是包含的,上面有例子,三字词也包含,比如查询 “中城药”百度错误提示:”中成药”,修改查询为”重城药”,还是提示”中成药” ,再次修改查询 “重城要”,百度依然提示”中成药”. 那么4字词汇呢?

百度还是会给你提示的,下面是个例子:
输入:静华烟云 提示 京华烟云
输入:静话烟云 提示 京华烟云
输入:静话阎晕 提示 京华烟云

那 么更长的词汇是否提 示呢?也提示,比如我输入: “落花世界有风军”,这个查询是什么意思,估计读过古诗的都知道,看看百度的提示”落花时节又逢君”,这说明什么?说明同音词词典包含不同长度的同音词信息,另外也说明了百度的核心中文处理技术,也就是那个词典,还真挺大的.

但是,如果用户输入的 查询由两个或者两个以上子字符串构成,那么百度的错误提示功能就罢工了,比如输入查询”哀体”,百度提示”艾提 挨踢”,但是.输入为 “我 哀体 “,则没有任何错误提示.

还有一个比较重要的问题:如果汉字是多音字那么怎么处理?百度呢比较偷懒,它根本就没有对多音字做处理.我们来看看百度的一个标注拼音的错误,在看这个错误前先看看对于多音字百度是怎么提示错误的,我们输入查询”俱长”,百度提示”剧场 局长”, “俱长”的拼音有两个:”ju zhang /ju chang” ,可见如果是多音字则几种情况都提示..现在我们来看看错误的情况, 我们输入查询”剧常”,百度提示”:剧场局长”,提示为”剧场”当然好解释,因为是同音字,但是为什么 “局长”也会被提示呢?这说明百度的同音字词典有错误,说明在”ju chang”这个词条里面包含”局长”这个错误的同音词.让我们顺藤摸瓜,这个错误又说明什么问题呢?

说明百度的同音词典是自动生成的,而且没有人工校对.还说明在自动生成同音词典的过程中,百度不是根据对一篇文章标注拼音然后在抽取词汇和对应的拼音信息获得的,而是完全按照某个词典的词条来标注音节的,

所 以对于多音字造成的错误无法识别出来,如果是对篇章进行拼音标注,可能就不会出现这种很容易发现的错误标注. 当然还有另外一种解释,就是”局长”是故意被百度提示出来可能的正确提示词汇,因为考虑到南方人”zh”和 “ch”等前后鼻音分不清么,那么是这样的么?我们继续测试到底是何种情况.是百度有错误还是这是百度的先进的算法?

我们考虑词汇”长 大 “,故意错误输入为”赃大”,如果百度考虑到了前后鼻音的问题,那么应该会提示”长大”,但是百度提示是”藏大”.这说明什么?说明百度并没有考虑前后鼻音问题,根本就是系统错 误. 我们输入查询”悬赏”,故意将之错误输入为”悬桑”,没有错误提示,说明确实没有考虑这种情况.前鼻音没有考虑,那么后鼻音考虑了么,我们输入”:经常”,故意改为后鼻音 “经缠”,百度提示为”经产 经忏”,还是没有考虑后鼻音.这基本可以确定是百度系统的错误导致.

根据以上推 导, 我们可以得出如下结论:百度是将分词词典里面每个词条利用拼音标注程序标注成拼音,然后形成同音词词典,所以两个词典是同样大的 ,而且这个词典也随着分词词典的增长而在不断增长. 至于标注过程中多音字百度没有考虑,如果是多音字就标注成多个发音组合,通过这种方式形成同音词词典.这样的同音词词典显然包含着很多错误.

最后一个问题:百度对于英文进行拼写检查么?让我们试试看,输入查询”china”,不错,搜到不少结果,专注中文搜索的百度还能搜索到英文,真是意外的惊喜.变换一下查询”chine”,会更加意外惊喜的给我们提示”china”吗?

百 度提示的是: 吃呢持呢,原来是不小心触发了百度的拼音搜索功能了.那么拼音搜索和中文检查错误是否采用同一套同音词词典呢,让我们来实验一下,搜索”rongji”, 百度提示” 榕基 溶剂 容积”,OK,换个中文查询”容机”,百度提示” 榕基溶剂容积”,看来使用的是同一套同音词词典.也就是说百度的中文纠错和拼音检索使用的机制相同,中文纠错多了一道拼音注音的过程而已.难道这就是传说中那个百度的”事实上是一个无比强大的拼音输入法”的拼音提示功能么?

最后让我们总结归纳一下百度的拼写检查系统:
后台作业:
(1) 前面的文章我们说过,百度分词使用的词典至少包含两个词典一个是普通词典,另外一个是专用词典(专名等),百度利用拼音标注程序依次扫描所有词典中的每个词条,然后标注拼音,如果是多音字则把多个音都标上,比如”长大”,会被标注为”zhang da/chang da”两个词条.
(2)通过标注完的 词条,建立同音词词典,比如上面的”长大”,会有两个词条: zhang daà长大” , chang daà长大.
(3)利用用户查询LOG频率信息给予每个 中文词条一个权重;
(4)OK,同音词词典建立完成了,当然随着分词词典的逐步扩大,同音词词典也跟着同步扩大;

拼写 检查:
(1)用户输入查询,如果是多个子字符串,不作拼写检查;
(2)对于用户查询,先查分词词典,如果发现有这个单词词条,OK, 不作拼写检查;
(3)如果发现词典里面不包含用户查询,启动拼写检查系统;首先利用拼音标注程序对用户输入进行拼音标注;
(4)对于标注好的拼音在同音词词典里面扫描,如果没有发现则不作任何提示;
(5)如果发现有词条,则按照顺序输出权重比较大的几个提 示结果;

拼音提示:
(1)对于用户输入的拼音在同音词词典里面扫描,如果没有发现则不作任何提示;
(2)如果 发现有词条,则按照顺序输出权重比较大的几个提示结果;

上面说过,经过分析得出百度的分词系统采用双向最大匹配分词,但是后来发现推理过程中存在一个漏洞,而且推导出来的百度分词算法步骤还是过于繁琐,所以进一步进行分析,看看是否前面的推导有错误.

那么以前的分析有什么漏洞呢?
我们推导百度分词有反向最大匹配的依据是百度将”北京华烟云”分词为<北,京华烟云>,从这里看好像采用了反向最大匹配,因为正向最大匹配的结果应该是<北京,华,烟云>,但是由此就推论说百度采用了双向最大匹配还是太仓促了,前面文章我们也讲过,百度有两个词典,一个普通词典,一个专有词典,而且是专有词典的词汇先切分,然后将剩余片断交给普通词典去切分.所以上面的”北京华烟云”之所以被切分成<北,京华烟云>,另外一个可能是:京华烟云这个词汇是在专有词典里面存储的,所以先分析,这样得出”京华烟云”,剩下”北”,没什么好切分的,所以输出<北,京华烟云>.

这里只是假设,那么是否确实”京华烟云”在专有词典呢?我们再看一个例子”山东北京华烟云”,百度切分的结果是<山 东,北,京华烟云 >,如果”京华烟云”在普通词典,如果是反向切分,那么结果应该是<山,东北,京华烟云>,如果是正向切分应该是<山东,北京, 华,烟云>,无论如何都分不出<山东,北,京华烟云>.这说明什么?
说明”京华烟云”是在那个专有词典,所以先切分出”京华烟云”,然后剩下的”山东北”交由普通词典切分,明显是正向最大匹配的结果输出<山东,北>.当然按照我们在第一篇文章的算法推导”山东北”的切分也会得出<山东,北>的结论,但是明显比正向最大匹配多几个判断步骤,既然效果一样,另外一个更加简洁的方法也能说得通,那当然选择简便的方法了.所以初步判断百度采取的是正向最大匹配.

我们继续测试采用何种分词算法,为了减少专有词典首先分词造成的影响,那么查询里面不能出现相对特殊的词汇,构筑查询”天才能量级”,这里应该没有专有词典出现过的词汇,百度切分为<天才,能量,级>,看来是正向最大匹配的结果.另外,如果所有查询词汇都出现在专有词典,那么采取的是何种方法?这样首先就得保证词汇都出现在专有词典,这么保证这一点呢?

我们构 造查询”铺陈晓东方”,百度切分为<铺,陈晓东,方>,可以看出 “陈晓东”是在专有词典的所以先切分出来.另外一个例子 “山东京城”,百度切分为<山东,京城>,说明”东京”是在普通词典的.OK,构造查询”陈晓东京华烟云”,通过前面分析可以看出两个词汇都在专有词典里面,百度切分为<陈晓东,京华烟云>,说明对于专有词典词汇也是采取正向最大匹配或者双向最大匹配.那么使用反向最大匹配了吗? 构造查询例子”陈晓东方不败”,首先我们肯定”陈晓东”和”东方不败”都是在专有词典出现的,如果是正向切分,那么应该是<陈晓东,方,不败 >或者<陈晓东,方,不,败>如果是反向切分则是<陈,晓,东方不败>,可以看出百度的切分是<陈晓东,方,不败 >或者<陈晓东,方,不,败>,说明采用的是正向最大匹配.通过分析,百度的词典不包含”不败”这个单词,所以实际上百度的切分结果是 <陈晓东,方,不,败>,很明显这和我们以前推导的算法是有矛盾的,所以以前的分析算法确实有问题,所以结论是百度采取的是正向最大匹配算法.

重新归纳一下百度的分词算法系统:首先用专有词典采用最大正向匹配分词,切分出部分结果,剩余没有切分交给普通词典,同样采取正向最大匹配分词,最后输出结果.

另外,GOOGLE也是采用正向最大匹配分词算法,不过好像没有那个专用词典,所以很多专名都被切碎了.

从这点讲,GOOGLE在中文词典构建上比百度差些,还需要加把子力气才行,不过这也不是什么多难的事.
标签:搜索引擎算法, 百度

Tuesday, January 12, 2010

HBase中Bloom Filter的使用_乘物游心

HBase中Bloom Filter的使用_乘物游心
HBase中Bloom Filter的使用
2009-02-12 11:26

HBase中Bloom Filter的使用

作者:马士华 发表于:2008-02-29 18:54 最后更新于:2008-03-01 17:06
版权声明:可以任意转载,转载时请务必以超链接形式标明文章原始出处和作者信息。
http://www.hadoop.org.cn/hbase/hbase-bloom-filter/

  BigTable是Google的一个分布式的结构化数据存储系统.如果你不懂什么是BigTable.请看美人他爹的这篇文章.HBase是在Hadoop上的建立一个跟BigTable相仿的一个系统.正像BigTable在使用布隆过滤器减少磁盘访问来提高效率.HBase同样使用布隆过滤器来提高效率.我们先来看看布隆过滤器的误差算法,然后再来解释HBase中如何使用布隆过滤器.

布隆过滤器不会有错判(Flase Negative), 可能有误判(False Positive). 我们来算一下我们认为能够接受的误判概率. 假设Hash函数是理想的, 也就是说, 函数值是均一分布的, Bloom Filter 长为 m bits, 那么对于一个输入, 某一位没被设置的概率是image002.gif 而我们一共有 k个独立不相关的Hash函数, 所以这一位保持为 0的概率应该是image005.gif 假如我们一直插入了 n个元素进来, 某一位是0的概率就是image007.gif .用1 减去它, 就是这一位是1 的概率了. 如果我们这时候开始测试元素是否在集合中而发生了错误, 就是说, 明明元素不在集合里面可是Hash 过后每一位都是1.这个的概率就是image009.gif , 假设m=20,n=1,k=8算出来的错误率是0.00013955336951317957 (Linux Bash: echo "(1-e(-8*1/20))^8"| bc -l).

在HBase的Wiki中对于如何计算BloomFilterDescriptor的参数描述的不太清楚,即如何确定number-of-values.其实HBase使用布隆过滤器是在建立表的列的时候指定.通过使用布隆过滤器将对每一次列中数据的磁盘访问先做一次判断来减少磁盘访问,对于频繁访问的列将提升很大的性能.当一个HRegion中当HStore中的HStoreFile大于设定值hbase.hregion.max.filesize的大小时,指派这个HRegion调用closeAndSplit()方法.一个HRegion最多只能是 hbase.hregion.max.filesize指定的文件大小.而HBase使用的布隆过滤器是在HStoreFile中调用来判断应用程序所请求的单元格数据是否在磁盘中存储.这就是说在 HBase使用的布隆过滤器取决于hbase.hregion.max.filesize指定的文件最多在这个列能够存储多少个单元格的数据(如果这个列是压缩存储的话,要计算压缩后的数量).假设我们一个 HRegion保存10000单元格,Hash函数大小为8,我们决定错误率为0.00001.即k=8,容错率为.通过计算则当m=295555时,其容错率为0.000009999973377382059符合我们的要求.那么m就是BloomFilterDescriptor中vectorSize的参数,k就是nbHash的参数,这就是我们建立表的列中BloomFilterDescriptor(final BloomFilterType type, final int vectorSize,final int nbHash)的构造函数的参数.如果我们使用单个参数的构造函数BloomFilterDescriptor(final BloomFilterType type,final int numberOfEntries),我们给定numberOfEntries一个任何的值,假设n=10000,k=4(默认),m = Math.ceil(number-of-values * 4 / ln(2))=57708。按算法构建的布隆过滤器其容错率为0.06左右。

相关文章

* 2008-06-26 -- HBase的概念和性能选项 (5)
* 2008-05-29 -- Hadoop Summit Video (3)
* 2008-08-20 -- Hadoop中的子项目Zookeeper能做什么 (6)
* 2008-08-07 -- 函数式编程范式-MapReduce (3)
* 2008-07-02 -- pig语言 (2)

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google... - Google Docs

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一
些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并
不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。
下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好
的处理方法,欢迎与我讨论。

1.Bloom filter

适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集

基本原理及要点:
对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,
查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的
结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位
会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个
counter数组代替位数组,就可以支持删除了。

还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个
数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少
要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数
组里至少一半为 0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底
的对数)。

举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同
元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通
常都是节省的。

扩展:
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否
全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位
扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将
其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G
,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,
如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这
样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大
大简单了。

2.Hashing

适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存

基本原理及要点:
hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开
地址法,opened addressing。

扩展:
d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2
-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2
分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计
算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[
key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少
的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存
储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同
时查找两个位置。

问题实例:
1).海量日志数据,提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进
行统计。

3.bit-map

适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码

扩展:bloom filter可以看做是对bit-map的扩展

问题实例:

1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出
现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个
2bit-map。

4.堆

适用范围:海量数据前n大,并且n比较小,堆可以放入内存

基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当
前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样
最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,
这样可以扫描一遍即可得到所有的前n元素,效率很高。

扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。

问题实例:
1)100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

5.双层桶划分

适用范围:第k大,中位数,不重复或重复的数字

基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步
确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个
例子。

扩展:

问题实例:
1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域
(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利
用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落
到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同
时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域
中的那些数就可以了。

实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程
度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^
20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可
以直接利用direct addr table进行统计了。

6.数据库索引

适用范围:大数据量的增删改查

基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。
扩展:
问题实例:


7.倒排索引(Inverted index)

适用范围:搜索引擎,关键字查询

基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词
在一个文档或者一组文档中的存储位置的映射。

以英文为例,下面是要被索引的文本:
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的反向文件索引:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what", "is" 和 "it" 将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档
有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档
占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向
了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向
的关系。

扩展:

问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字
搜索。

8.外排序

适用范围:大数据的排序,去重

基本原理及要点:外排序的归并方法,置换选择 败者树原理,最优归并树

扩展:

问题实例:
1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存
限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,
所以可以用来排序。内存可以当输入缓冲区使用。

9.trie树

适用范围:数据量大,重复多,但是数据种类小可以放入内存

基本原理及要点:实现方式,节点孩子的表示方式

扩展:压缩实现。

问题实例:
1).有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件
的query都可能重复。要你按照query的频度排序 。

2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的
字符串。请问怎么设计和实现?

3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不
超过3百万个,每个不超过255字节。

10.分布式处理 mapreduce

适用范围:数据量大,但是数据种类小可以放入内存

基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

扩展:

问题实例:

1).The canonical example application of MapReduce is a process to count the
appearances of

each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially
with a "1" value by

the Map function, using the word as the result key. The framework puts
together all the pairs

with the same key and feeds them to the same call to Reduce, thus this
function just needs to

sum all of its input values to find the total appearances of that word.

2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。

3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如
何找到N^2个数的中数(median)?


经典问题分析

上千万or亿数据(有重复),统计其中出现次数最多的前N个数据,分两种情况:可一次
读入内存,不可一次读入。

可用思路:trie树+堆,数据库索引,划分子集分别统计,hash,分布式计算,近似统
计,外排序

所谓的是否能一次读入内存,实际上应该指去除重复后的数据量。如果去重后数据可以
放入内存,我们可以为数据建立字典,比如通过 map,hashmap,trie,然后直接进行
统计即可。当然在更新每条数据的出现次数的时候,我们可以利用一个堆来维护出现次
数最多的前N个数据,当然这样导致维护次数增加,不如完全统计后在求前N大效率高。

如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情
形,可以做的改变就是将字典存放到硬盘上,而不是内存,这可以参考数据库的存储方
法。

当然还有更好的方法,就是可以采用分布式计算,基本上就是map-reduce过程,首先可
以根据数据值或者把数据hash(md5)后的值,将数据按照范围划分到不同的机子,最好
可以让数据划分后可以一次读入内存,这样不同的机子负责处理各种的数值范围,实际
上就是map。得到结果后,各个机子只需拿出各自的出现次数最多的前N个数据,然后汇
总,选出所有的数据中出现次数最多的前N个数据,这实际上就是reduce过程。

实际上可能想直接将数据均分到不同的机子上进行处理,这样是无法得到正确的解的。
因为一个数据可能被均分到不同的机子上,而另一个则可能完全聚集到一个机子上,同
时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个,我们将
1000万的数据分布到10台机器上,找到每台出现次数最多的前 100个,归并之后这样不
能保证找到真正的第100个,因为比如出现次数最多的第100个可能有1万个,但是它被
分到了10台机子,这样在每台上只有1千个,假设这些机子排名在1000个之前的那些都
是单独分布在一台机子上的,比如有1001个,这样本来具有1万个的这个就会被淘汰,
即使我们让每台机子选出出现次数最多的1000个再归并,仍然会出错,因为可能存在大
量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上,而是要根据hash
后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。

而外排序的方法会消耗大量的IO,效率不会很高。而上面的分布式方法,也可以用于单
机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。
处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排
序的归并过程。

另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际
中出现最多的那些词作为一个字典,使得这个规模可以放入内存。

转载请注明出处:http://bbs.xjtu.edu.cn
作者phylips@bmy

参考文献:
http://blog.csdn.net/jiaomeng/archive/2007/03/08/1523940.aspx d-Left Hashing
http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
http://en.wikipedia.org/wiki/Bloom_filter
http://hi.baidu.com/xdzhang_china/blog/item/2847777e83fb020229388a15.html 应用Bloom Filter的几个小技巧
http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95

发信人: cshyh (Zakklars), 信区: Algorithm
标 题: Re: 大数据量,海量数据 处理方法总结
发信站: 兵马俑BBS (Thu Nov 26 20:02:27 2009), 本站(bbs.xjtu.edu.cn)

嗯 比较不错啊 想了下比较常见的里面没写赫赫有名的二叉排序树

发信人: phylips (星星||一年磨十剑), 信区: Algorithm
标 题: Re: 大数据量,海量数据 处理方法总结
发信站: 兵马俑BBS (Thu Nov 26 22:36:34 2009), 本站(bbs.xjtu.edu.cn)

恩 可以加下
另外i/o 优化方面并没有太多涉及,如果对于这方面谁比较有心得可以补充一下

发信人: appsony (懒羊羊), 信区: Algorithm
标 题: Re: 大数据量,海量数据 处理方法总结
发信站: 兵马俑BBS (Thu Nov 26 22:38:05 2009), 本站(bbs.xjtu.edu.cn)

很不错啊 比较全面。bloom filter确实不错,刚看managing gigabytes这本书,里面
讲索引的一种建法也是这种思想。

发信人: appsony (懒羊羊), 信区: Algorithm
标 题: Re: 大数据量,海量数据 处理方法总结
发信站: 兵马俑BBS (Thu Nov 26 22:41:11 2009), 本站(bbs.xjtu.edu.cn)

话说应对这类面试题,把编程珠玑研究透彻就差不多了。平常用的话,Managing
gigabytes这本书值得推荐一下。



发信人: phylips (星星||一年磨十剑), 信区: Algorithm
标 题: 面试题目-大数据量专题
发信站: 兵马俑BBS (Thu Nov 26 16:30:44 2009), 本站(bbs.xjtu.edu.cn)

1. 给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找
出A,B文件共同的URL。

2. 有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件
的query都可能重复。要你按照query的频度排序

3. 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存
限制大小是1M。返回频数最高的100个词

4.海量日志数据,提取出某日访问百度次数最多的那个IP。

5.2.5亿个整数中找出不重复的整数,内存空间不足以容纳这2.5亿个整数。

6.海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。

7.怎么在海量数据中找出重复次数最多的一个

8.上千万or亿数据(有重复),统计其中出现次数最多的前N个数据。

统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可
以提高效率,比如 出现次数>数据总数/N的一定是在前N个之内

9.1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的
字符串。请问怎么设计和实现?

10.一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前十个
词。请给出思想,给时间复杂度分析。

11.一个文本文件,也是找出前十个最经常出现的词,但这次文件比较长,说是上亿行
或者十亿行,总之无法一次读入内存,问最优解。

12.有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件
的query都可能重复要按照query的频度排序

13.100w个数中找最大的前100个数

14.寻找热门查询:
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的
长度为1-255字节。假设目前有一千万个记录,
这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。
一个查询串的重复度越高,说明查询它的用户越多,
也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程,算法,以及算法的复杂度。

15.一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)?

本文由phylips@bmy收集整理,转载请注明出处http://bbs.xjtu.edu.cn
谢谢合作。


有一个1G的数组a,元素是0到2^30-1的自然数.
我想把他打乱成随机的顺序,最简单的实现(代码最简)和时间最优的实现分别是什么?


求算法:从一千万个数字里找出100个最大的数的最快算法。

seabao 于 Wed Oct 21 18:58:06 2009 提到:

堆排序 这种解决方案都是堆排序。

都是面试惹得祸...

还有其他点可以忽悠:

1. 多线程去做会更快。
2. 比较fashion的解决方案,MapReduce 我不知道怎么实现,但是大致意思还好。

如果能把MapReduce的问题了解清楚,这样回答的话,估计大部分面试官都能被忽悠住。

duoduolo 于 Thu Oct 22 09:16:47 2009 提到:

第k大元素那个算法么

BlueBore 于 Fri Oct 23 09:18:58 2009 提到:

这个数据量很小,用堆排或快排,平均复杂度都是O(n),快排常数因子更小些

如果数据量大了选择并行算法,把问题拆开,分配到t个计算节点上,分别堆排,把本
来n*lg100的问题转化为t个(n/t)lg100的问题,最后归并的代价是O(lgt),所以总的代
价就是O(lgt+n/t),最后根据数据的规模选择t的大小。

http://blog.csdn.net/lanphaday/archive/2008/12/18/3547899.aspx

http://space.cnblogs.com/question/4423/

Wednesday, January 6, 2010

Re: amazon onsite 面经 - 未名空间(mitbbs.com)

3. Design a fight ticket booking system.

4. 老板说网站很慢怎么办?
老板说数据库很慢怎么办?

Problems like No4 are very popular. These are testing your problem solving
skill, troubleshooting skill and past experience.

Mostly it is not expected to have perfect answer for these problems. Most
likely how you troubleshoot these problems. For example, for application
being slow:
- checking what has changed (data volume, code, hardware, database?)
- adding metrics collection/profiling [to figure out which part is taking
most of the time]
- adding monitoring [when it is slow, can you trigger some alarm to take
snapshot of the system for future analysis? Can you add some code to send
email/page to get immediate attention]
- review design/architecture/database for optimizations and improvments
- if you figured out which part is slow, how do you address that. what are
the possible senarios?
= SQL/DB related? improve SQL? SQL plan? Index? DB tricks?
= Memory, CPU, I/O,network throttled? how to improve?
= Parallelize? Algorithm optimization? etc etc.

skill, troubleshooting skill and past experience.


= Memory, CPU, I/O,network throttled? how to improve?
= Parallelize? Algorithm optimization? etc etc."

未名空间(mitbbs.com) - 海外华人第一门户

未名空间(mitbbs.com) - 海外华人第一门户
主要功能介绍
版面 即论坛或讨论区,本站共有500个左右版面,详见“主要版面介绍”。
移民专栏 汇集众多专业移民律师,律师在MITBBS上设有自己的专栏,及时提供移民相关信息及提供各类移民签证、绿卡申请、身份转换、公民入藉等服务。
未名博客 可自由撰写文章,轻松上传图片。
新闻中心 每天上百条国内外新闻及时更新,设有:八卦、时政、财经、科技、体育、娱乐、移民等频道。
未名精华区 本站最大特色之一,汇集建站十多年来的各类精品杂谈评论、美文佳作、重大爆料、热门大坑,及各类工作、生活、学习的实用生活信息。。
未名形象秀 网友ID的“大头贴”,一个虚拟的购物之地,需要未名 “伪币”来购买。
未名俱乐部 己的私人俱乐部,建立自己的圈子。每个ID 可建3个俱乐部。
伪币 未名空间虚拟的流通货币,可用于购买形象秀,开建俱乐部,购买博彩、基金等。
主要版面介绍
(1) 新闻中心
中国新闻(ChinaNews) 讨论国内时事、政治问题及社会热点事件,是网友进行政治辩论的主要版面之一。(此版对国内屏蔽)
史海钩沉(History) 饭后茶余评点逸闻轶事,日落月升闲侃稗官野史,急叩键盘激辩争议人物,轻点鼠标也敢借古讽今。
军事天地(Military) 本版围绕军事方面展开讨论,包括兵器装备、战略战术、军事史,以及其他与军事有关的政治经济文化话题。(此版对国内屏蔽)
海峡两岸(TheStrait) 讨论海峡两岸政治经济文化联系与发展,评论热点时事新闻,争辩台湾问题走向等。(此版对国内屏蔽)
民主沙龙(Salon) 本版以时政评论类话题为主,倡导言论自由,谈论民主制度、国家政体、自由平等。(此版对国内屏蔽)
美国新闻(USANews) 围绕美国本土政治、经济、文化新闻展开讨论,关注与美国华人生活密切相关的时事变化。
全球瞭望(WorldNews) 是网友关注国际上重大政治经济新闻、热点事件的空间,交流网友对国际时局动态的看法与观点。
(2) 海外生活

车轮上的传奇(Automobile)
又称“汽车版”,讨论话题主要围绕车型、车况、买卖车保险、事故处理诸多经验等。
证券中国(ChinaStock) 为讨论国内证券、股票投资的场所。
电子商务(ebiz) 利用网络平台,做生意想赚钱的朋友们喜欢的版面,此版常用术语:医院、医生、护士、病人。
我爱我家(Family) 又称“饭米粒”,聚集该版块的话题多围绕两性/ 婚姻/伦理/家庭,发在该版面的贴子易得到回应,回贴讨论众多;常有大坑,颠峰时期,来自饭米粒的讨论常占据BBS十大话题榜首。
画饼充饥(Food) 厨房设备餐具的选购以及各色菜肴的做法及展示平台,该版多举办各色菜肴大比拼。
落地生根(Immigration) 有关美、加移民以及移民期间非移民身份相关话题,在这里你也可以知道办绿卡的基本流程,以及名词缩写如PD/RD/LUD等。
待字闺中(JobHunting) 找工作相关问题,如简历、着装、面试等问题的讨论。
家居生活(Living) 买卖房屋遇到的问题、租房中与房东的交涉讨论,房屋贷款、房屋装修咨询。
我爱宝宝(NextGeneration) 将为人母的孕期情况及经验分享,已为人母的宝宝成长记录。
为人父母(Parenting) 多是父母的育儿心得,尤其是选择幼儿园小学及学校中宝宝与同学或老师之间发生的问题讨论居多。
省钱一族(PennySaver) 汇集了购物指南、省钱秘籍、及时的coupon等有用信息,coupon的谐音哭胖一词也由此而来。
博士后(Postdoc) 博士后的天地,期间和老板的关系、经费、论文、毕业后的何去何从等讨论。
海归(Returnee) 讨论中美发展,国内几大城市的房价、教育、薪水等问题,若干年后留外还是海归的话题经久不衰。
股海弄潮-美股(Stock) 和ChinaStock相对应,此版主要讨论美股的开户指南、经验教训、股票走势预测等各类信息。
签证(Visa) 主要分享签证经验及咨询签证中遇到的各类问题。
上班一族(Working) 上班过程中和老板、同事之间发生的故事。
(3) 华人世界
新加坡(Singapore) 生活在具有“花园城市”之称的狮城,不能不来Singapore版,这里汇集了狮城的美食、购物,游玩等生活信息与指南,让你更多地认识新加坡,更好地在新加坡生活。
美国(USA) 为初来乍到的华人留学生提供了购物、餐饮、交通等衣食住行的信息及各种版聚联谊、工作及学习的交流平台。覆盖了海外华人比较集中的38个主要地区:如三藩、洛杉矶,西雅图、纽约等。
加拿大(CAN) 分享生活、工作、学习经验,交流衣、食、住、行生活信息。目前包括加拿大、温哥华,多伦多,蒙特利尔等主要地区。
(4) 体育健身
篮球(Basketball) 一个供网友讨论篮球运动、篮球明星、发表观点的版面,可以在观看篮球比赛中实时参与热烈的交流活动。
健身俱乐部(Fitness) 健身从来不是一个人的事情,在本版可以和朋友们一起交流健身经验、方法、技巧,一起分享健身的效果,在相互鼓励中完美健身。
大学体育(NCAA) 本版讨论话题围绕北美大学校园的篮球比赛、橄榄球比赛等,网友在此交流各自喜欢的大学体育明星、校际联赛等。
滚吧,足球!(Soccer) 卡卡、梅西、C罗谁会成为下一个球王?巴萨、皇马、阿森纳、曼联、AC米兰,您是谁的忠实拥趸?五大联赛哪个更让您痴迷?……来这里与拥有共同爱好的朋友们一起分享足球的激情!
(5) 娱乐休闲
星座物语(astrology) 了解星座知识,查看星座运势,八卦明星星座以及多样性、趣味性的星座测试,星座物语版伴随您走过每一段人生的旅途,享受生活的乐趣。
美丽时尚(Fashion) 这里都是爱时尚、爱生活、独立自尊、见地独到、热力四射的前沿女性,探究时下最新服饰和秀场;这里也有最IN的服饰潮流、时尚大牌、美容护肤、健康减肥的新鲜法宝和交流体会;这里每期都有让你心动并行动的时尚活动,来到这儿你的生活也摩登起来。
虚拟人生(Game) 是一个尽情游戏、快乐交友、珍藏回忆、分享心情的平台。
无限影话(Movie) 影视是生活的一扇窗户,这里有最新的电影资讯、最有争议的电影人物风采及百家争鸣的精彩影评;欢迎来到无限影话版,说说心中的电影,分享您的观影评论!
天籁之音(Music) 本着“自娱自乐、积极向上、欣赏音乐、结交同好”的宗旨,欢迎所有版友播放自己喜欢的音乐作品,欢迎任何表演及演唱形式!
户外活动(Outdoors) 户外活动已成为一种时尚,在这里无论你是初入江湖,还是资深驴友,都可以找到需要的信息,分享大家旅途的欢乐;新朋友成了老朋友,老朋友又有了新朋友。
摄影器材(PhotoGear) 无论是选购器材,还是评测,这里既是新手的起点,也有高手们的评测、见解;使您购买器材时事半功倍,评测器材时畅所欲言。
摄影作品(PhotoForum) 你是摄影发烧友吗?您对摄影作品有不一样的视角评论吗?您愿意把您的作品跟大家分享吗?来到PhotoForum版,一切疑问将会得到答案。因为这里汇集了摄影与旅行的随感录,优秀摄影作品集锦。
四海为家(Travel) “Travel”版是一部旅行百科全书,在这里能找到周游世界的各种攻略,也有驴友们的闲侃杂谈、旅行中的趣事见闻等。
(6) 情感杂想
梦里花落知多少(Dreamer) Mitbbs匿名发文版,该版文风独特,因其匿名的发文之特色,使得众多发文网友不忌曝露个人之真实性情,常有骇世佳作。
肚皮舞运动(Joke) 本版最大的特色是把生活中及站上各版的笑料与众多网友一起分享,自然会带给你意想不到的真实的快乐。
情爱幽幽(Love) 又称“老虎版”,是恋爱中的男女倾诉衷肠,情感求助的天地。
心有所宠(pets) 分享宠物安全、饲养、医疗、保健、购买、领养,法律等经验与知识,交流宠物生活起居的故事,图片,视频,传递宠物与人的快乐相处的温馨版面。多有美图。
鹊桥(Piebridge) 为海外的单身男女架起了一座免费沟通的桥梁,更不乏有成功的典范。话题丰富,常有大坑。
(7) 文学艺术
宗教信仰(Belief) 聚集人群多为基督徒。但信仰不同,经常会出现有神无神信与不信及对圣经观点等有争议性话题的辩论。
谈古论金,黄梁一梦(paladin) 鼓励原创,多以武侠小说为主,常有连载。
文海拾贝(Literature) 文学气息浓厚,作品多为诗歌、散文,书评等。
散文.原创文学版(Prose) 仅限原创散文,作品多情感细腻、文笔优美,其中不乏长篇著作。
性意识(Sex) 男女性生活的讨论,常有美文佳作。
佛道儒(Wisdom) 讨论或解说一切传统文化和智慧结晶:佛学、道学、诸子百家,各种新流派,新思想及法家、名家,墨家等话题的研究与讨论。
(8) 校友联谊
伯克利(Berkeley) 伯克利大学在华人圈远近闻名,许多留学生在这里书写自己的生活感受。
复旦大学(FDU) 多数校友不定期的来到版内版聚,已成为校友联谊的纽带。
南开大学(NKU) 多是回忆在大学里的趣事,讨论与南开有关的新闻。
北京大学(PKU) 北大的学术氛围,人文气息对北大校友有着深远的影响,也是广大校友热衷讨论的焦点。
清华大学(THU) 本版是校友区人气最旺的一个版面,针对当前的热点事件都能展开积极讨论。
中国科学技术大学(USTC) 很多校友通过本版,举办校庆、聚会等活动。
(9) 乡里乡情
我爱北京天安门(Beijing) 不管你是不是北京人,只要你喜欢北京,向往北京或者生活在北京,那么就加入到我爱北京天安门(Beijing)的行列中吧,一起说道说道北京的人儿、北京的事儿、北京的味儿。
巴山蜀水(ChuanYu) 你晓不晓得四川?晓得的话随便说两句三。我们有九寨沟、黄龙、卧龙、四姑娘山,我们还有青稞、牦牛、变脸和川剧。
九头鸟(Hubei) 如果你是湖北人,那么在这里你可以自由发挥,把你喜欢的小吃,拍过的照片,玩过的地方介绍给大家。如果你是外地人,那么这在这里你可以了解到一个不一样的湖北,不是电视上介绍的,而是真实的湖北。
上海风情(Shanghai) 在上海生活的日子,我感觉不出自己有多么喜欢这座城市,可当我离开上海去到另一个城市,我却突然发现它的每一个弄堂,每一句吴侬软语都深深的印在了我的生命里,让我夜夜梦回……
浙江(Zhejiang) 这里是我们的家,我们是她成长的见证者,记录者,欢迎大家到浙江(Zhejiang)记录分享生活中开心的、悲伤的、生气的、苦闷的鸡毛蒜皮&流言蜚语。
(A)电脑网络
家有苹果(Apple) 讨论与所有苹果公司产品及周边有关的话题,大家一起互相学习,共享相关资源,希望这里能成为每个苹果fan的家。Everything About APPLE!
葵花宝典(Programming) 共同学习,共同进步,讨论或探讨编程方面的技术应用和问题解决,发现网络编程的乐趣。
(B)学术学科
会计审计(Accounting) 服务于华人accountant community,交流和互换学习资料。
生物学(Biology) 生物学实验交流,选学校、选老板、选工作及回国发展讨论。
商学院(Business) MBA及就业问题讨论。
化学(Chemistry) 有关化学的学术交流、资源共享,寻求文献。
经济(Economics) 经济研究及学校专业排名,一切与经济和金融相关的讨论。
医学职业(MedicalCareer) 本版是为在美申请医学院、在读医学院、以及考USMLE申请住院医生职位的同胞提供交换心得和交流经验的场地!
金融工程(Quant) 金融方面的书籍推荐,话题讨论,工作offer的选择与经验交流。
(0)本站系统
站长工作室(sysop) 报告站内BUG、寻求站长帮助、发表意见建议,用户与站方的沟通平台。
版主之家(Board) 版主申请、竞选、任免,新版申请、版务公告等专用版块。
投诉(Complain) 申请、受理站内的各类投诉,及弹劾版主,举报变形虫的地方。
本站特色词汇
小钻风 原是西游记里的巡山小妖的名字. 这里是为公共站务ID mitbbs起的外号。此ID刚刚由walklooktalk在sysop版公布时,大家决定叫它总钻风,因为其职能类似于总版主,但小钻风这个名字最后沿用了下来。这个ID由walklooktalk在北京的雇员轮流值班,为提高论坛流量而到各版挑选文章置顶,也经常越过各版版主处理版务,由此引起很多怨言。但由于是雇员,从不像其他站长一样耍态度。
LD 领导,一般指配偶,引申出小LD,指家里的孩子。
LP、LG 老婆、老公的简称。
WSN Family版经常出现的称呼.可男可女.猥琐男或者猥琐女的简称.特点是心理幼稚但是不阴暗, 行为诡异但是不偏激。
外F女 外嫁女的贬义用法,F估计代表英文Fuck,原指海外华人中对洋人盲目推崇进而随便与其上床的女生,后泛指因为绿卡或金钱等不纯目的而找洋人做男友或老公的中国女子,通常在Dreamer版上出现。这个词应该是源于对一些外嫁女子在网上炫耀自己的涉外爱情和家庭经历,而引起某些人群的不平。
坑 意等同于英文词"TROLL",泛指那些投人所好有争议/夸大其词/或者纯属编造的贴子,来引发网友讨论,这样的贴子常被人称为"坑",发此类贴子的行为被称为"挖坑"。
发包子 凡文章获得版主加精 (M上),发文用户自动获得10元伪币。借此,网友们管发文章让版主加精为发包子行为,一个包子等于10伪币。
毛上、搞上 毛上指的是版主将版面的文章mark以保留该文章,标记符号为m,故取其谐音称为毛上;而搞上是指版主将版面文章加入文摘区,标记符号为g,故取其谐音称为搞上。
饭米粒 特指“我爱我家”版(FAMILY的谐音读法)。
离 饭米粒版对婚姻问题的标准回复,后来范围扩展至所有问题。很多id上来不看文章,照着原贴就是一个字“离”。后来版主StoryTeller试图令行禁止,成效不大。
八区 泛指"中国新闻"(CHINANEWS),"世界新闻"(WORLDNEWS),以及SALON,HISTORY,MILITARY等等版面,八区的叫法源于这些版面最初在TELNET界面下统属第8版块,该版块因涉及时事新闻较多,持不同见解的人言词激烈,很多时候八区版面火药味浓重,易引发争吵,"八区"在不少网友眼中常常被视为吵架的地方。
BT 源于拼音"变态"。起初用于自认为正常人类对被认为非正常人类的蔑称. 此称谓最初出现于mitbbs dreamer版2000年左右,那个时候dreamer风格转换,忧郁的文青正在被一些被称为新生代变态的新ID为首的新成员所代替。后来这个词逐渐在 MITBBS被泛化,现在已经变成英语里面"dude"一样的称呼。BT 也指 Balance Transfer 多用于Money版。
88一下 即八卦一下。
PENG 源于"肚皮舞运动"(Joke)版面,该用法源于大约1999年左右的一则新闻:英国陆军因为军费缺乏,打靶演习无法用实弹,只好在射击时口中发出射击声音。ID katy时任Joke斑竹,并转载了该新闻,建议今后见到老笑话就用"Peng"表示。"PENG"一词后扩散至整个BBS,涵盖面也扩大到任何性质的贴子,不仅仅只是笑话贴,包括贴子是重复的或者某人说过同样的话,都可以用PENG来表达。后来在 情爱幽幽(Love)版继续演化为 “BENG”。
奔 最初称为裸奔。一般是指网友在版面上帖出自己的照片供大家欣赏取乐,有时也有如交友等特殊目的。常用的口号有:某某奔一个!奔上十大!你小你先! 等等. 2003-2004年度裸本成为mitbbs维护人气的一个重要节目,前著名女光棍,资深ID Janet曾制作并且不定期发布裸奔大全。
晒 指专门show东西物件的,照片里没有人物只有物品。
胖子 Shopping(购物版)的常用词汇,指购物的时候使用的折扣券。因为美国商店的折扣券,英文为“Coupon”和中文“酷胖”或“哭胖”谐音,久而久之网友就改称之为“胖子”,而且显得更加琅琅上口。
死呆婆 美国著名办公用品商Staples的中文谐音,源自Mitbbs人气大版Shopping。该店因良好的客户服务、遍及美国城乡的销售网络、以及诸多的促销活动而深受Shopping版网友的推崇,某些网友的第一桶金即出自Staples。Staples目前已进入中国市场,其中文官方译名为“史泰博”。
RenPinWenTi 人品问题(rpwt)的另类表达。mitbbs南来北往,网友众多,模糊拼音的使用受到广大网友的普遍好评。
医院 ebay, 鉴于购物天堂(Shopping)版版主禁止在版上讨论ebay买卖,所以大家用“医院”这词代替ebay。典故出自前任汽车版主,shopping版资深ID coven在shopping版用隐晦的语言讲述自己在ebay因做托被封杀id及株连马甲的故事。另外由于ebay鱼龙混杂,故又用厕所一称呼代替。
病人 ebay 购物者
JHQ 精华区,多用于提示新手参考精华区,而不是一味问问题。
buffet deal (简称 buffet) ebiz版 形容一笔交易的利润的量词。。。指获利,够享用一顿buffet...非常形象。
BSO Bloodly Show off 不管人说啥都可以re:bso!)
更详细介绍请见本站网站地图:[点击查看]