A Text-Extraction Based Summarizer

We present an automated method of generating human-readable summaries from a variety of text documents including newspaper articles, business reports, government documents, even broadcast news transcripts. Our approach exploits an empirical observation that much of the written text display certain regularities of organization and style, which we call the Discourse Macro Structure (DMS). A summary is therefore created to reflect the components of a given DMS. In order to produce a coherent and readable summary we select continuous, well-formed passages from the source document and assemble them into a mini-document within a DMS template. In this paper we describe an automated summarizer that can generate both short indicative abstracts, useful for quick scanning of a list of documents, as well as longer informative digests that can serve as surrogates for the full text. The summarizer can assist the users of an information retrieval system in assessing the quality of the results returned from a search, preparing reports and memos for their customers, and even building more effective search queries.

Introduction
A good summarization tool can be of enormous help for those who have to process large amounts of documents. In information retrieval one would benefit greatly from having content-indicative quick-read summaries supplied along with the titles returned from search. Similarly, application areas like routing, news on demand, market intelligence and topic tracking would benefit from a good summarization tool.
Perhaps the most difficult problem in designing an automatic text summarization is to define what a summary is, and how to tell a summary from a non-summary, or a good summary from a bad one. The answer depends in part upon who the summary is intended for, and in part upon what it is meant to achieve, which in large measure precludes any objective evaluation. A good summary should at least be a good reflection of the original document while being considerably shorter than the original thus saving the reader valuable reading time.
In this paper we describe an automatic way to generate summaries from text-only documents. The summarizer we developed can create general and topical indicative summaries, and also topical informative summaries.
Our approach is domainindependent and takes advantage of certain organization regularities that were observed in news-type documents. The system participated in a thirdparty evaluation program and turned out to be one of the top-performing summarizers. Especially the quality/length ratio was very good since our summaries tend to be very short (10% of the original length).
The summarizer is still undergoing improvement and expansion in order to be able to summarize a wide variety of documents. It is also used successfully as a tool to solve different problems, like information retrieval and topic tracking.

Task Description and Related Work
For most of us, a summary is a brief synopsis of the content of a larger document, an abstract recounting the main points while suppressing most details. One purpose of having a summary is to quickly learn some facts, and decide what you want to do with the entire story. Depending on how they are meant to be used one can distinguish between two kinds of summaries. Indicative summaries are not a replacement for the original text but are meant to be a good reflection of the kind of information that can be found in the original document. Informative summaries can be used as a replacement of the original document and should contain the main facts of the document. Independent of their usage summaries can be classified as general summaries or topical summaries.
A general summary addresses the main points of the document ignoring unrelated issues. A topical sum-mary will report the main issues relevant to a certain topic, which might have little to do with the main topic of the document. Both summaries might give very different impressions of the same document. In this paper we describe a summarizer that summarizes one document, text only, at a time. It is capable of producing both topical and generic indicative summaries, and topical informative summaries. Our early inspiration, and a benchmark, have been the Quick Read Summaries, posted daily off the front page of New York Times on-line edition (http://www.nytimes.com). These summaries, produced manually by NYT staff, are assembled out of passages, sentences, and sometimes sentence fragments taken from the main article with very few, if any, editorial adjustments. The effect is a collection of perfectly coherent tidbits of news: the who, the what, and when, but perhaps not why. Indeed, these summaries leave out most of the details, and cannot serve as surrogates for the full article. Yet, they Mlow the reader to learn some basic facts, and then to choose which stories to open.
This kind of summarization, where appropriate passages are extracted from the original text, is very efficient, and arguably effective, because it doesn't require generation of any new text, and thus lowers the risk of misinterpretation. It is also relatively easier to automate, because we only need to identify the suitable passages among the other text, a task that can be accomplished via shallow NLP and statistical techniques. Nonetheless, there are a number of serious problems to overcome before an acceptable quality summarizer can be built. For one, quantitative methods alone are generally too weak to deal adequately with the complexities of natural language text. For example, one popular approach to automated abstract generation has been to select key sentences from the original text using statistical and linguistic cues, perform some cosmetic adjustments in order to restore cohesiveness, and then output the result as a single passage, e.g., (Luhn 1958) (Paice 1990) (Brandow, Mitze, & Rau 1995) (Kupiec, Pedersen, & Chen 1995). The main advantage of this approach is that it can be applied to almost any kind of text. The main problem is that it hardly ever produces an intelligible summary: the resulting passage often lacks coherence, is hard to understand, sometimes misleading, and may be just plain incomprehensible. In fact, some studies show (cf. (Brandow, Mitze, & Ran 1995)) that simply selecting the first paragraph from a document tends to produce better summaries than a sentence-based algorithm.
A far more difficult, but arguably more "human-like" method to summarize text (with the possible exception of editorial staff of some well-known dailies) is to comprehend it in its entirety, and then write a summary "in your own words." What this amounts to, computationally, is a full linguistic analysis to extract key text components from which a summary could be built. One previously explored approach, e.g., (Ono, Sumita, & Miike 1994) (McKeown & Radev 1995, was to extract discourse structure elements and then generate the summary within this structure. In another approach, e.g., (DeJong 1982) (Lehnert 1981) pre-defined summary templates were filled with text elements obtained using information extraction techniques. Marcu (Marcu 1997a) uses rhetorical structure analysis to guide the selection of text segments for the summary; similarly Teufel and Moens (Teufel & Moens 1997) analyze argumentative structure of discourse to extract appropriate sentences. While these approaches can produce very good results, they are yet to be demonstrated in a practical system applied to a reasonable size domain. The main difficulty is the lack of an efficient and reliable method of computing the required discourse structure.

Our Approach
The approach we adopted in our work falls somewhere between simple sentence extraction and textunderstanding, although philosophically we are closer to NYT cut-and-paste editors. We overcome the shortcomings of sentence-based summarization by working on paragraph level instead. Our summarizer is based on taking advantage of paragraph segmentation and the underlying Discourse Macro Structure of News texts. Both will be discussed below.

Paragraphs
Paragraphs are generally self-contained units, more so than single sentences, they usually address a single thought or issue, and their relationships with the surrounding text are somewhat easier to trace. This notion has been explored by Cornell's group (Salton et al. 1994) to design a summarizer that traces inter-paragraph relationships and selects the "best connected" paragraphs for the summary. Like in Cornell's system, our summaries are made up of paragraphs taken out of the original text. In addition, in order to obtain more coherent summaries, we impose some fundamental discourse constraints on the generation process, but avoid a full discourse analysis.
We would like to note at this point that the summarization algorithm, as described in detail later, does not explicitly depend on nor indeed require input text that is pre-segmented into paragraphs. In general, any length passages can be used, although this choice will impact the complexity of the solution. Lifting well-defined paragraphs from a document and then recombining them into a summary is relatively more straightforward than recombining other text units. For texts where there is no structure at all, as in a closed-captioned stream in broadcast television, there are several ways to create artificial segments. The simplest would be to use fixed word-count passages. Or, content-based segmentation techniques may be applicable, e.g., Hearst's Text-Tiling (Hearst 1997).
On the other hand, we may argue that essentially any length segments of text can be used so long as one could figure out a way to reconnect them into paragraph-like passages even if their boundaries were somewhat off. This is actually not unlike dealing with the texts with very fine grained paragraphs, as is often the case with news-wire articles. For such texts, in order to obtain an appropriate level of chunking, some paragraphs need to be reconnected into longer passages. This may be achieved by tracking co-references and other text cohesiveness devices, and their choice will depend upon the initial segmentation we work up from.

Discourse Macro Structure of a Text
It has been observed, eg., (Rino & Scott 1994), (Weissberg & Buker 1990), that certain types of texts, such as news articles, technical reports, research papers, etc., conform to a set of style and organization constraints, called the Discourse Macro Structure (DMS) which help the author to achieve a desired communication effect. For instance, both physics papers and abstracts align closely with the Introduction-Methodology-Results-Discussion-Conclusion macro structure. It is likely that other scientific and technical texts will also conform to this or similar structure, since this is exactly the structure suggested in technical writing guidebooks, e.g. (Weissberg & Buker 1990). One observation to make here is that perhaps a proper summary or an abstract should reflect the DMS of the original document. On the other hand, we need to note that a summary can be given a different DMS, and this choice would reflect our interpretation of the original text. A scientific paper, for example, can be treated as a piece of news, and serve as a basis of an un-scientific summary.
News reports tend to be built hierarchically out of components which fall roughly into one of the two categories: the What-Is-The-News category, and the optional Background category. The Background, if present, supplies the context necessary to understand the central story, or to make a follow-up story self-contained. The Background section is optional: when the background is common knowledge or is implied in the main news section, it can, and usually is omitted. The What-Is-The-News section covers the new developments and the new facts that make the news. This organization is often reflected in the summary, as illustrated in the example below from NYT 10/15/97, where the highlighted portion provides the background for the main news:

SPIES JUST WOULDN'T COME IN FROM COLD WAR, FILES SHOW
Terry Squillacote was a Pentagon lawyer who hated her job. Kurt Stand was a union leader with an aging beatnik's slouch. Jim Clark was a lonely private investigator. [A 200-page affidavit filed last week by] the Federal Bureau of Investigation says the three were out-of-work spies for East Germany. And after that state withered away, it says, they desperately reached out for anyone who might want them as secret agents.
In this example, the two passages are nonconsecutive paragraphs in the original text; the string in the square brackets at the opening of the second passage has been omitted in the summary.
Here the human summarizer's actions appear relatively straightforward, and it would not be difficult to propose an algorithmic method to do the same. This may go as follows: 1. Choose a DMS template for the summary; e.g., Background+News.
Select appropriate passages from the originM text and fill the DMS template.
Assemble the summary in the desired order; delete extraneous words.
It is worth noting here that the backgroundcontext passage is critical for understanding of this summary, but as such provides essentially no relevant information except for the names of the people involved. Incidentally, this is precisely the information required to make the summary self-contained, if for no other reason than to supply the antecedents to the anaphors in the main passage (the three, they).

The Algorithm
The summarizer can work in two modes: generic and topical. In the generic mode, it simply summarizes the main points of the original document. In the topical mode, it takes a user supplied statement of interest, a topic, and derives a summary related to this topic. A topical summary is thus usually different from the generic summary of the same document. The summarizer can produce both indicative and informative summaries. An indicative summary, typically 5-10% of the original text, is when there is just enough material retained from the original document to indicate its content. An informative summary, on the other hand, typically 20-30% of the text, retains all the relevant facts that a user may need from the original document, that is, it serves as a condensed surrogate, a digest.
The process of assembling DMS components into a summary depends upon the complexity of the discourse structure itself. For news or even for scientific texts, it may be just a matter of concatenating components together with a little of "cohesiveness glue", which may include deleting some obstructing sentences, expanding acronyms, adjusting verb forms, etc. In a highly specialized domain (e.g., court rulings) the final assembly may be guided by a very detailed pattern or a script that conforms to specific style and content requirements.
Below we present a 10-step algorithm for generating summaries of news-like texts. This is the algorithm underlying our current summarizer. The reader may notice that there is no explicit provision for dealing with DMS structures here. Indeed, the basic Background+News summary pattern has been tightly integrated into the passage selection and weighting process. This obviously streamlines the summarization process, but it also reflects the notion that news-style summarization is in many ways basic and subsumes other more complex summarization requirements. is selected for a summary, passage N must also be selected. Link consecutive passages until all references are covered.
Score all passages, including the linked groups with respect to the paragraph-search query. Assign a point for each co-occurring term. The goal is to maximize the overlap, so multiple occurrences of the same term do not increase the score.
Normalize passage scores by their length, taking into account the desired target length of the summary. The goal is to keep summary length as close to the target length as possible. The weighting formula is designed so that small deviations from the target length are acceptable, but large deviations will rapidly decrease the passage score. The exact formulation of this scheme depends upon the desired tradeoff between summary length and content. The following is the basic formula for scoring passage P of length I against the passagesearch query Q and the target summary length of t, as used in current version of our summarizer:
Discard all passages with length in excess of 1.5 times the target length. This reduces the number of passage combinations the summarizer has to consider, thus improving its efficiency. The decision whether to use this condition depends upon our tolerance to length variability. In extreme cases, to prevent obtaining empty summaries, the summarizer will default to the first paragraph of the original text.
Combine passages into groups of 2 or more based on their content, composition and length. The goal is to maximize the score, while keeping the length as close to the target length as possible.
Any combination of passages is allowed, includ-(5) ing non-consecutive passages, although the original ordering of passages is retained. If a passage (6) attached to another through a background link is included into a group, the other passage must also be included, and this rule is applied recursively. We need to note that the background links work only one way: a passage which is a background for (7) another passage, may stand on its own if selected into a candidate summary. S7: Recalculate scores for all newly created groups. This is necessary, and cannot be obtained as a sum of scores because of possible term repetitions. Again, discard any passage groups longer than 1.5 times the target length. Add premium scores to groups based on the inverse degree of text discontinuity measured as a total amount of elided text material between the passages within a group. Add other premiums as applicable.
s8: Rank passage groups by score. All groups become candidate summaries.
s9: Repeat steps s6 through s8 until there is no change in top-scoring passage group through 2 consecutive iterations. Select the top scoring passage or passage group as the final summary.

Implementation and some Examples
The summarizer has been implemented in C++ with a Java interface as a demonstration system, primarily for news summarization. At this time it can run in both batch and interactive modes under Solaris, and it can also be accessed via Web using a Java compatible browser. Below, we present a few example summaries. For an easy orientation paragraphs are numbered in order they appear in the original text. TOPIC: Hidden cameras used in news reporting (4) Roone Arledge, the president of ABC News, defended the methods used to report the segment and said ABC would appeal the verdict.
"They could never contest the truth" of the broadcast, Arledge said. "These people were doing awful things in these stores." Wednesday's verdict was only the second time punitive damages had been meted out by a jury in a hidden-camera case. It was the first time punitive damages had been awarded against producers of such a segment, said Neville L. Johnson, a lawyer in Los Angeles who has filed numerous hidden-camera cases against the major networks.
Many journalists argue that hidden cameras and other undercover reporting techniques have long been necessary tools for exposing vital issues of public policy and health. But many media experts say television producers have overused them in recent years in a push to create splashy shows and bolster ratings. The jurors, those experts added, may have been lashing out at what they perceived as undisciplined and overly aggressive news organizations.
In a postscript to the Cold War, the American governmentowned corporation that is charged with reselling much of Russia's military stockpile of uranium as civilian nuclear reactor fuel turned down repeated requests this year to buy material sufficient to build 400 Hiroshima-size bombs.
The incident raises the question of whether the corporation, the U.S. Enrichment Corp., put its own financial interest ahead of the national-security goal of preventing weapons-grade uranium from falling into the hands of terrorists or rogue states.
The corporation has thus far taken delivery from Russia of reactor fuel derived from 13 tons of bomb-grade uranium. "The nonproliferation objectives of the agreement are being achieved," a spokesman for the Enrichment Corp. said.
But since the beginning of the program, skeptics have questioned the wisdom of designating the Enrichment Corp. as Washington's "executive agent" in managing the deal with Russia's Ministry of Atomic Energy, or MINATOM.
Domenici, chairman of the energy subcommittee of the Senate Appropriations Committee, which is shepherding the privatization plan through Congress, was never informed of the offer by the administration. After learning of the rebuff to the Russians, he wrote to Curtis asking that the Enrichment Corp. "be immediately replaced as executive agent" and warning that "under no circumstances should the sale of the USEC proceed until this matter is resolved." Once Domenici entered the fray, the administration changed its tune.
Curtis sent a letter to Domenici stating that all the problems blocking acceptance of the extra six tons had been solved. People close to the administration said that the Enrichment Corp. has now been advised to buy the full 18-ton shipment in 1997. Moreover, Curtis quickly convened a new committee to monitor the Enrichment Corp. for signs of foot-dragging.

Evaluation
Our program has been tested on a variety of newslike documents, including Associated Press newswire messages, articles from the New York Times, The Wall Street Journal, Financial Times, San Jose Mercury, as well as documents from the Federal Register, and the Congressional Record. The summarizer is domain independent, and it can be easily adapted to most European languages. It is also very robust: we used it to derive summaries of thousands of documents returned by an information retrieval system. Early results from these evaluations indicate that the summaries generated using our DMS method offer an excellent tradeoff between time/length and accuracy. Our summaries tend to be shorter and contain less extraneous material than those obtained using different methods. This is further confirmed by the favorable responses we received from the users. Thus far there has been only one systematic multisite evaluation of summarization approaches, conducted in early 1998, organized by U.S. DARPA 1 in the tradition of Message Understanding Conferences (MUC) (DAR 1993) and Text Retrieval Conferences (TREC) (Harman 1997a), which have proven successful in stimulating research in their respective areas: information extraction and information retrieval. The summarization evaluation focused on content representativeness of indicative summaries and comprehensiveness of informative summaries. Other factors affecting the quality of summaries, such as brevity, readability, and usefulness were evaluated indirectly, as parameters of the main scores. For more details see (Firmin & Sundheim 1998).
The indicative summaries were scored for relevance to pre-selected topics and compared to the classification of respective full documents. In this evaluation, a summary was considered successful if it preserved the original document's relevance or nonrelevance to a topic. Moreover, the recall and precision scores were normalized by the length of the summary (in words) relative to the length of the original document, as well as by the clock time taken by the evaluators to reach their topic relevance decisions. The first normalization measured the degree of content compression provided by the summaries, while the second normalization was intended to gauge their readability. The results showed a strong correlation between these two measures, which may indicate that readability was in fact equated with meaningfulness, that is, hard to read summaries were quickly judged non-relevant.
For all the participants the best summaries scored better than the fixed-length summaries. When normalized for length our summarizer had the highest score for best summaries and took the second place for fixed-length summaries. The F-scores for indicative topical summaries (best and fixed-length) were very close for all participants. Apparently it is easier to generate a topical summary then a general summary. Normalizing for length did move our score 1(The U.S.) Defense Advanced Research Projects Agency up, but again, there was no significant difference between participants.
The informative (topical) summaries were scored for their ability to provide answers to who, what, when, how, etc. questions about the topics. These questions were unknown to the developers, so systems could not directly extract facts to satisfy them. Again, scores were normalized for summary length, but no time normalization was used. This evaluation was done on a significantly smaller scale than for the indicative summaries, simply because scoring for question answering was more time consuming for the human judges than categorization decisions. This evaluation could probably be recast as categorization problem, if we only assumed that the questions in the test were the topics, and that a summary needs to be relevant to multiple topics.
Informative summaries were generated using the same general algorithm with two modifications. First, the expected summary length was set at 30% of the original, following an observation by the conference organizers while evaluating human generated summaries. Second, since the completeness of an informative summary was judged on the basis of it containing satisfactory answers to questions which were not part of the topic specification, we added extra scores to passages containing possible answers: proper names (who, where) and numerics (when, how much). Finally, we note that the test data used for evaluation, while generally of news-like genre, varied greatly in content, style and the subject matter, therefore domain-independence was critical.
Again our summarizer performed quite well, although the results are less significant since the experiment was carried out on such a small scale. The results were separated out for three different queries. For two queries the system was very close to the top performing system, and for the third query the system had an F-score of about 0.61 versus 0.77 for the best system.
In general we are quite pleased with the summarizer performance, especially since our system was not trained on the kind of texts that we had to summarize.

Related
Work and Future Work The current summarizer is still undergoing improvement and adaptation in order to be able to summarize more than a single text news document at a time. At the same time we are investigating how summarization can be used in related but different problems. Both will be described below.
A better and more flexible summarizer Currently our summarizer is especially tuned for English one-document text-only news summarization. While we are still working on improving this, we also want the system to be able to summarize a wider variety of documents. Many challenges remain, including summarization of non-news documents, multimodal documents (such as web pages), foreign language documents and (small or large) groups of documents covering one or more topics. Typically, a user needs summarization the most when dealing with a large number of documents. Therefore, the next logical step is to summarize more than one documents at a time. At the moment we are focusing on multi-document (crossdocument) summarization of English text-only news documents. Just as for single-document summarization, multi-document summarization can be generic or topical and indicative or informative. Other factors that will influence the types of summary are the number of documents (a large versus a small set) and the variety of topics discussed by the documents (are the documents closely related or can they cover very different topics). Presentation of a multi-document offers a wide variety of choices. One could create one large text summary that gives an overview of all the main issues mentioned in all summaries. Or perhaps give different short summaries for similar documents. If the number of documents is very large it might be best to create nested summaries with high-level descriptions and the possibility to 'zoom in' on a subgroup with a more specific summary. A user will probably want to have the ability to trace information in a summary back to its original document; source information should be a part of the summary. If one views summarization in the context of tracking a topic, the main goal of the summary might be to show the new information every next document contains, while not repeating information already mentioned in previous documents. Another type of summary might highlight the similarities documents have (e.g., all these documents are on protection of endangered species) and pointing out the differences they have (e.g., one on bald eagles, some on bengal tigers,..). As one can see, there are many questions to be answered and the answers depend partially on the task environment the summarizer will be used in.
Currently we are focussing on summarizing a small set of text-only documents (around 20) all on a similar topic. The summary will reflect the main points/topics discussed by the documents. Topics discussed by more than one document should only be mentioned once in the summary together with its different sources. When generating the summary we want to ensure coherence by placing related topic close to each other. The main issues we are addressing is the detection of similar information in order to avoid repetition in the summary and the detection of related information in order to generated a coherent summary. This work is right now in progress. Our next step will be summarizing large amounts of similar information.
Applying summarization to different problems Information retrieval (IR) is a task of selecting documents from a database in response to a user's query, and ranking these documents according to relevance. Currently we are investigating the usage of summarization in order to build (either automatically or with the help of the user) more effective information need statements for an automated document search system. The premise is quite simple: use the initial user's statement of information need to sample the database for documents, summarize the returned documents topically, then add selected summaries to the initial statement to make it richer and more specific. Adding appropriate summaries can be either done by the user who reads the summaries or automatically. Both approaches are described in our other paper appearing in this volume.
The task of tracking a topic consists of identifying those information segments in a information stream that are relevant to a certain topic. Topic tracking is one of the three main tasks in the TDT (Topic Detection and Tracking) tasks that we hope to use our summarizer for. The information stream consists of news, either from a tv broadcast or a radio broadcast. Speech from these programs has been recognized by a state-of-the-art automatic speech recognition system and also transcribed by human transcriptionists. A topic is defined implicitly by a set of training stories that are given to be on this topic. The basic idea behind our approach is simple. We use the training stories to create a set of keywords (the query). Since we process continuous news the input is not segmented into paragraphs or any other meaningful text unit. Before applying our summarizer each story is divided into equal word-size segments. We summarize every story using our query, and use similarity of the summary to the query to decide whether a story is on topic or not. We are still in the process of refining our system and hope to have our first results soon. Initial results suggest that this is a viable approach. It is encouraging to notice that the absence of a paragraph structure does not prevent the system from generating useful summaries.

CONCLUSIONS
We have developed a method to derive quick-read summaries from news-like texts using a number of shallow NLP techniques and simple quantitative methods. In our approach, a summary is assembled out of passages extracted from the original text, based on a pre-determined Background-News discourse template. The result is a very efficient, robust, and portable summarizer that can be applied to a variety of tasks. These include brief indicative summaries, both generic and topical, as well as longer informative digests. Our method has been shown to produce summaries that offer an excellent tradeoff between text reduction and content preservation, as indicated by the results of the governmentsponsored formal evaluation.
The present version of the summarizer can handle most written texts with well-defined paragraph structure. While the algorithm is primarily tuned to newspaper-like articles, we believe it can produce news-style summaries for other factual texts, as long as their rhetorical structures are reasonably linear, and no prescribed stylistic organization is expected. For such cases a more advanced discourse analysis will be required along with more elaborate DMS templates.
We used the summarizer to build effective search topics for an information retrieval system. This has been demonstrated to produce dramatic performance improvements in TREC evaluations. We believe that this topic expansion approach will also prove useful in searching very large databases where obtaining a full index may be impractical or impossible, and accurate sampling will become critical.
Our future development plans will focus on improving the quality of the summaries by implementing additional passage scoring functions. Further plans include handling more complex DMS's, and adaptation of the summarizer to texts other than news, as well as to texts written in foreign languages. We plan further experiments with topic expansion with the goal of achieving a full automation of the process while retaining the performance gains.


Discovering Lexical Information by Tagging Arabic Newspaper Text

In this paper we describe a system for building an Arabic lexicon automatically by tagging Arabic newspaper text. In this system we are using several techniques for tagging the words in the text and figuring out their types and their features. The major techniques that we are using are: finding phrases, analyzing the affixes of the words, and analyzing their patterns. Proper nouns are particularly difficult to identify in the Arabic language; we describe techniques for isolating them.

INTRODUCTION
A lexicon is considered to be the backbone of any natural language application. It is an essential basis for parsing, text generation, and information retrieval systems. We cannot implement any of these applications or others in the natural language area without having a good lexicon. All natural language processing systems need a lexicon full of explicit information [Ahlswede and Evens, 1988;Byrd et al., 1987McCawley, 1986. The best way to find the necessary lexieal information, we believe, is to extract it automatically from text.
We are developing a part-of-speech tagger for Arabic newspaper text. We are testing it on a corpus developed by Ahmad Hasnah [1996] based on text given to Illinois Institute of Technology, by the newspaper, Al-Raya, published in Qatar. The questions we address here are how to build an efficient techniques for automating the tagger system, what techniques and algorithms can be used in finding the part of speech and extracting the features of the word. When it comes to the Arabic language there are problems and challenges that are not present in English or other European languages.
Newspaper articles are full of proper nouns that need special rules to tag them in the text, because the Arabic language does not distinguish between lower and upper case letters, which leave us with a big problem in recognizing proper nouns in Arabic text.
The lack of vowels in the text we are using creates big problems of ambiguity. Different vowels change the word from noun to verb and from one t39e of noun to another; they also change the meaning of the word. For example, the following two words have the same letters with the same sequence but with different vowels. The result is different meanings.
, ";~ k(a)t(a)b wrote ' "< k(u)t(u)b books Most published Arabic text is not vowelized with the exception of the Holy Quran and books for children.
Some words in Arabic text begin with one, two, three, or four extra letters that constitute articles or prepositions. For example, the following word consists of two parts: the particle (a preposition letter) that is attached to the beginning of the noun while it is not part of it and the noun itself.
(on occasion) ".-q~t~. -~ ~ + ".-q~tz, We need to identify these cases in the text and deal with them in a perceptive way.
In this paper we are trying to find answers to these challenges through building a tagger system whose main function is to parse an Arabic text, tag the parts of speech, and find out their features to build a lexicon for this language. Three main techniques used in this system for tagging the words are: finding phrases (verb phrases, noun phrases, and proper noun phrases), analyzing the affixes of the word, and analyzing its pattern.

TAGGING VERB AND NOUN
There are several signs in the Arabic language that indicate whether the word is a noun or a verb. One of them is the affix of the word: some of the affixes are used x~ith verbs; some of them are used with nouns; and some of them are used xvith verbs and nouns. A lot of research projects have used this technique to find the part of speech of a word. Andrei Mikheev [1997] used a technique for fully automatic acquisition of rules that guess possible part-of-speech tags for unknown words using their starting and ending segments. Several types of guessing rules are included: prefix morphological rules and suffix morphological rules. Zhang and Kim [1990] developed a system for automated learning of morphological word function rules. This system divided a string into three regions and inferred from training examples their correspondence to underlying morphological features. More advanced word-guessing methods use word features such as leading and trailing word segments to determine possible tags for unknown words. Such methods can achieve better performance, reaching a tagging accuracy of up to 85% on unknown words for English [Brill 1992;Weischedel et al., 1993]. Another sign that indicates whether a word is a noun or a verb is the pattern. In the Arabic language the patterns function as an important guide in recognizing the type of the word; some of these patterns are used just for nouns; some of them are usedjustfor verbs; and others are used for both nouns and verbs. One more sign comes from grammatical rules; several grammatical rules can be used to distinguish between nouns and verbs, some letters in the Arabic language (letters of signification are similar to prepositions in the English language) mark the nouns; others mark the verbs

TAGGING PROPER NOUNS
Constructing lexical entries for proper nouns is not less important than defining and analyzing common nouns, verbs, and adjectives for supporting natural language applications. The semantic categories of proper nouns are crucial information for text understanding [Wolinski et al., 1995] and information extraction [Cowie and Lehnert,1996]. They are also used in information retrieval systems [Paik et al.,1993]. A number of studies have shown the usefulness of lexical-semantic relationships in information retrieval systems [Evens et al., 1985;Nutter et al., 1990;Abu-Salem, 1992]. The lexicalsemantic relationships are also important in other applications like question-answering systems [Evens and Smith, 1978]. Rau [1991] argues that proper nouns not only account for a large percentage of the unkno~aa words in a text, but also are recognized as a crucial source of information in a text for extracting contents, identifying a topic in a text, or detecting relevant documents in information retrieval. Wacholder [1997] analyzed the types of ambiguitystructural and semantic -that make the discovery of proper names in the text difficult. Jong-Sun Kim and Evens [1995] built a natural language processing system for extracting personal names and other proper nouns from the Wall Street Journal. We have classified the proper nouns that we found in the A1-Raya newspaper as follows:

TAGGER SYSTEM
This system consists of four main subsystems beside the database (lexicon): Tokenizer System: This system locates a document and isolates the words (tokens).
Type-Finder System: The main function of this system is to get the token from the tokenizer system, to get some information about it from the morphology analyzer system, to go through several tests one by one until we find the part of speech of the word.
Feature-Finder System: This system is responsible for finding the features of the word (gender, number, person, tense). It sends the word to the morphology analyzer system, gets back information about it, analyzes this information, and figures out the features of the word.
Morphology analyzer system: This system is used by both the t3q0e-finder system and the feature-finder system to analyze the suffix and prefix of the word. This system contains three subprograms: one for nouns, one for verbs, and one for particles. The main function of these algorithms is to isolate the affixes of the word and find the gender, number, person, and tense.
Database (the lexicon): We started from a hand built lexicon created by Khalid Alsamara [ 1996], which our system uses and constantly updates. The lexicon consists of the main table and several tables connected to it one for verbs, one for nouns, one for particles. We add several tables for proper nouns.

TOKENIZER SYSTEM
We have implemented an algorithm that can isolate the punctuation marks as well as isolate the extra particles attached to the beginning of the word, while they are not part of it. We have classified the words in the Arabic language into eight categories with respect to their prefix. This system caries out three main steps: Isolate the word from the text, pass it to a certain algorithm to classify it, and with respect to this classification we run a certain algorithm to generate the token.

s. TYPE-FINDER SYSTEM
This system goes through several tests starting by checking the database, identifying the phrases, analyzing the affixes of the word, and analyzing its pattern.

PHRASE-FINDER TEST
After we check the database and discover that our token is absent, we move to the second test.
The phrase-finder test uses a set of grammatical rules that identify the phrases in the text. It looks for the phrases (verb phrase, noun phrase, and proper noun phrase) in the text, analyzes them and figures out the part of speech of the word.

Example:
Mrs. Diana made her visit to the computer conference, that is being held. for the first time in Chicatm This test determines the part of speech of all the underlined words.

CHECKING THE AFFIX PATTERNS
If the second test fails to identify the part of speech of our token, we continue to the third and the four test in sequence, for these taro tests we are using two techniques: analyzing the affixes of the word and finding its patterns.
First, we have classified affixes into two groups: • affix rule (A): if an affix occurs in a word we can surely determine the t3q)e of the word without any doubt.

AFFIX-RULE-(A) TEST
This third test gets the affix of the word from the morphology analyzer system and checks these affixes with affix rule (A

PATTERN-AFFIX-RULE-(B) TEST
The fourth test uses a combination of affix rule (B) and the pattems of the word. This test uses affix rule (B) to support the decision that will be taken from the pattern technique. It gets the affix of the word from the morphology analyzer system, checks the affix with affix rule (B)to find out if there is a match, finds the pattern of the word, analyzes it to find out the type that it is used for. We then go through the following

FEATURE-FINDER SYSTEM
This system sends the word and its t39e to the morphology, analyzer system, gets back morphological information about it (the affixes and the gender, number, person, and tense of the word), gets the pattern of the word, analyzes this information using a certain rules we have developed for this system, and finds the features.

CONCLUSION
We badly need a large integrated comprehensive lexicon. To achieve this goal we need to build this lexicon automatically. To build such a lexicon we are developing a part of speech tagger for Arabic text that extracts features of the words encountered. We have described three major techniques that we are using in this paper: finding phrases, analyzing the affixes oftheword, and analyzing its patterns. We have classified the proper nouns in the Arabic language to different categories, we used a new technique to tag them from the Arabic text by using the ke3-words. We developed a set of grammatical rules for this reason.