{'fraction_non_alphanumeric': 0.03004056109514957, 'fraction_numerical': 0.015928680074362007, 'mean_word_length': 4.7532814778804084, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Summarization Assistant for News Brief Services on Cellular Phones

A Chinese news summarization method is proposed in order to help humans deal with the message services of news briefs broadcast over cell phones. The problem to be solved here is unique because a strict length limit (69 or 45 characters) is imposed on the summaries for the message service. This requires some sort of automatic sentence fusion, rather than sentence selection alone. In the proposed method, important sentences were first identified based on the news content. They were matched against the news headline to determine a suitable position for concatenation with the headline to become candidates. These candidates were then ranked by their length and fitness for manual selection. In our evaluation, among 40 short news updates in the inside testing set, over 75% (80%) of the best candidates yield acceptable summaries without manual editing for the length limit of 69 (45) characters. These numbers, however, reduce to 70.7% (53.3%) for the outside testing set of 75 news stories of ordinary length. It seems that the shorter the length limit, the more difficult the problem of getting the summary from long stories. Nevertheless, the proposed method has the potential not only to reduce the cost of manual operation, but also to integrate and synchronize with other media in such services in the future.


Introduction
The popularity of cell phones in the Taiwan area has reached the highest rate in the world during the last few years. Over 23 million cell phone numbers were used as of June 2002, which is slightly more than the population of Taiwan (Wang, 2002). To better utilize this ubiquitous communication device, a number of content providers have provided Chinese news From the research perspective, the task defined above is a challenge for automatic document summarization. Previous studies have shown that the shorter the summary required, the lower the performance of machine-generated summary (Lin & Hovy, 2003), hence, the more difficult the problem is. The task of news brief summarization for cell phones falls into this difficult category. On the other hand, human summarization of news stories for cell phones is not really a difficult problem. As mentioned above, the main issue is whether one can achieve this task in a low-cost and efficient way. Strictly maintaining the length limit requires a human summarizer to pay attention to the number of characters already there while making the summarization. If a machine could suggest a number of summary candidates, each with its length shown, for human selection, not only would the human summarizer be relieved of such tedious work and improve his/her efficiency, but also the task would become less difficult for machine summarization.
This article proposes a Chinese news summarization technique to assist human summarizers in the above way, with the aim of meeting the considerations described above. Basically, our approach is a sentence fusion technique that merges the news headline with the body sentence that supplements the information carried by the headline. After a brief review of previous work in the next section, the detailed approach and its motivations are described. The performance is then evaluated and the results are shown. This is followed by a discussion of the strengths and weaknesses of the proposed method. Finally, we conclude this paper with

Related Work
Automatic news summarization techniques have been widely explored in recent years, such as the summarization tasks in DUC (DUC, n.d.) or in NTCIR (Fukusima, Okumura, & Nanba, 2002). Several practical systems (e.g. (Hovy & Lin, 1999;Evans, Klavans, & McKeown, 2004;Radev, Otterbacher, Winkel, & Blair-Goldensohn, 2005)) have been developed in the past decade. The summarization techniques used in most studies can be divided into two approaches: abstraction and extraction (Mani, 2001;Radev, Hovy & McKeown, 2002). In abstraction, advanced natural language processing (NLP) techniques are applied to analyze sentential information and then to generate concise sentences with proper semantics. Sophisticated NLP techniques, such as anaphora resolution, may be used and certain human maintained knowledge bases or corpora may be needed. In extraction, statistical techniques are applied to rank and select the text snippets for a summary. Due to its relatively low cost and high robustness across application domains and document genres, most summarization tasks adopt the extraction approach (Carbonell & Goldstein, 1998;Lin & Hovy, 2002, Tseng, et al, 2007. Nevertheless, abstraction-based methods move the summarization field from the use of purely extractive methods to the generation of abstracts that contain sentences not found in any of the input documents and also synthesize information across sources (Barzilay & McKeown, 2005). Thus, the need for an abstraction-based approach is sometimes inevitable.
Despite the vast literature already published, most of the studies are for English. Although some have focused on Chinese news (e.g. (Chen, Kuo, Huang, Lin & Wung, 2003)), none have been done for the problem discussed here. The problem to be solved in this paper is unique due to the facts that there is a strict length limit imposed and that the range of the length limit makes most simple sentence selection approaches invalid. Thus, an abstraction-based method or a similar one that requires sentence fusion or alteration is required.
For example, in (Takefumi, Hidetaka, & Hiroshi, 2003) the authors reported a deletion-based approach to summarize a Web news article for PC to another short article for cell phones for Japanese. There, the length limit of the short article ranges from 50 to 100 Japanese characters. The approach first computes the values of TFxIDF for each clause in advance. A few significant sentences from the original article are then extracted based on the TFxIDF values. After that, verbose descriptions corresponding to the leaves of the dependency trees, having the lowest TFxIDF, are removed from the sentences until the length of the result of summarization is within the limit.
An important issue in automatic summarization is the evaluation of machine-derived summaries. This is not an easy task. Two main approaches are commonly applied: intrinsic and extrinsic evaluation (Mani, 2001). In intrinsic evaluation, manually prepared answers or evaluation criteria are compared with those that are machine generated. In extrinsic evaluation, automated summaries are evaluated based on their performance or influence on other tasks, such as document categorization. We adopt the intrinsic approach here since it is obviously suitable for our task.

The Proposed Summarizer
To develop an automated Chinese news summarizer subject to the limitations of a cell phone, an understanding of the style of the news stories and how humans summarize them would be helpful. Table 1 lists three news examples and their English translations. As can be seen, these examples are short, with their bodies having only 1, 2, and 3 sentences, respectively. This is not uncommon for the stories to be transmitted to users' cell phones, although longer stories may be selected as well. Given such short stories, a human summarizer has very few clues as to rewrite the story thoroughly to fit the length limit. The best he or she can do may be to cut and paste the snippets from the news text with minimal editing to avoid garbling the original meaning.
The snippets to be cut and pasted can be enumerated then suggested by a computer for manual selection. Nevertheless, the possibilities of such enumeration would be huge if all substrings of the news text are blindly considered. As can be seen from the examples in Table  1, a Chinese sentence is often composed of several comma-separated clauses, which convey the meaning of the sentence in successive sequence. Chinese clauses are independent from each other in some circumstances and, thus, constitute a useful unit to be combined with others to make a new sentence. Although most of the combined sentences would be invalid, several of them would still be meaningful and sometimes more complete in content, especially for those from the beginning and ending clauses. Experts: World Population Set to Peak at 9 Billion The world's population will probably peak at about 9 billion around 2070 before it starts to decline, scientists predicted Wednesday.
Demographers at a think tank in Austria calculate that by the turn of the century the number of people on the planet will have dropped down to 8.4 billion people. The 10 year, $1 billion global scientific collaboration aims to identify and catalog all life in the oceans.
After their first three years of work, census scientists report over 15,300 species of fish in the sea and estimate 5,000 more are still unknown to science. Marine life census finds hundreds of new species; they estimate 5,000 more are still unknown to science.
Take the third story from Table 1 as an example. The headline has only 16 characters, falling short of the required length of 45 or 69. The other 3 sentences have 52, 63, and 49 characters, respectively. None of them alone is an ideal summary of the required length. Nevertheless, by concatenating the headline and the last clause of each body sentence, as shown in Table 2, each becomes a better choice for summaries of length 45.
It is noted that the simple Select-First-N strategy which usually has been the baseline method for most news summarization tasks would not work here. As can be seen from Table 1, if the first n characters were used as the summary, the underlined text in the first sentence of the story would be chosen as the summary for the length limit 45. These summaries, however, are incomplete in their meaning. If the first clauses (ending with a comma or period and no longer than n) were used as the summary, they may be still incomplete in meaning or too verbose to deliver the message even when their meanings are complete. For example, for the length limit 45, the first two clauses of the first story: "美國航空航太總署的科學家星期三 稱，新近在一顆遙遠的恒星周圍發現了水存在的痕跡" (38 characters) would be extracted based on the Select-First-N clause strategy. This, however, is inferior to the perfect summary "太空探測器在遙遠的恒星周圍發現水的痕跡，這可以成為第一個支援除我們自己存在地 外生命的證據。" (45 characters) which is extracted based on the heuristic rule shown in Table   2. In this example, the headline perfectly replaces the first two clauses, leaving more space for including the supplemental information in the final clause: "這可以成為第一個支援除我們 自己存在地外生命的證據。".
The above observation gives us clues to effectively enumerate the summary candidates. Nevertheless, there are other problems that need to be considered in order to further reduce the burden of human selection: (1) The number of suggested candidates should be fairly equal for each story. Long stories should not yield considerably more candidates than short ones. (2) The candidates should be ranked in some sense when they are suggested for selection.
To tackle these problems, we propose the following processing steps: Step 1: Sort all the sentences of a news story by their weights and select the best 5 sentences for use in the next step.
Step 2: Generate summary candidates by matching and combining each selected sentence with the news headline. Calculate the match scores and summary lengths.
Step 3: Sort the candidates by their lengths and scores. In Step 1, the weight of a sentence in a story of any length is determined by the accumulated weights of the keywords occurring in that sentence, as shown below:

News Brief Services on Cellular Phones
where tf w is the term frequency of keyword w and max_tf is the term frequency of the keyword which occurs most in the news story. Here, the keywords of a story are those headline words that remain from non-content-bearing word deletion and those maximally repeated patterns in the story that are extracted by Tseng's algorithm . Tseng has shown that Chinese news stories can contain many new keywords, almost 1/3 of repeated words are unknown to a lexicon of 123,226 terms. His algorithm ensures that unknown words can be extracted as well, as long as they occur at least twice in a document. In Step 2, since headlines are guides to a news story, they should be included in the beginning of the candidates. The ending clauses to be concatenated should supplement the content of the headline. This means that the beginning clauses of a body sentence should be as similar to the headline as possible. To spot the position for concatenation and to know the similarity, a dynamic programming (DP) technique is used.  (Levenshtein, 1966) is: where min is a function that returns the minimum of its 3 arguments, and c( , and 1 otherwise. The initial values for the distance are: A similarity function is defined in (Lopresti & Zhou, 1996) to convert the edit distance into the similarity: exp( d[n,j] / (d[n,j] -n) ), where exp is the exponent function. This similarity ranges from 0 to 1. We found, however, that its range does not distribute well for later comparison. Thus, it was changed into: where j denotes the j-th character (including the punctuation) of the body sentence. The new measure ranges from exp(-n/m) to 1.
The starting position (the position for concatenation) of the ending clauses is first determined by the comma which most closes the character with highest similarity. Since we favor length more than similarity (here, length is a direct measure that must be met, while similarity is just an approximation of the content similarity between the headline and the body sentence), the starting position is changed to its preceding or succeeding comma whenever such changes fit the length limit better. Figure 1 shows an example where the second row beneath the body sentence indicates an assumed similarity score for each character position. Although the last comma (defining the starting position of the proper ending clause) has a similarity score 0.5, higher than the one 92 Yuen-Hsien Tseng with 0.25, the desired ending clauses would start from the one with 0.25 since it fits the length limit better. This changes the summary candidate from "最好的一句，其實在最後一小句。", with 15 characters in length and 0.5 in similarity, into "最好的一句，看了以後，其實在最後 一小句。", with 20 characters in length and 0.25 in similarity.

Title:
最 好 的 一 句 Body Sentence: Sometimes, the last clause of each body sentence may be too long, causing all the concatenated candidates to exceed the required length. In this case, only the news headline will be generated as the output without any concatenation.
News stories are often written in a so-called pyramid style where the later the paragraph occurs, the more details it carries. Thus, better summaries often come from the first few sentences. Therefore, in our current implementation, we decrease the similarity of the summary candidates composed from the sentences other than the first two by a factor of 0.85, if the number of sentences in the story exceeds 3.

In
Step 3, the length of the summary candidate is divided by the required length limit (45 or 69) to yield the length ratio ranging from 0 to 1. Now, we come to a problem of determining the rank of these candidates based on their length ratios and similarities. Ideally, this problem can be solved by machine learning methods, but they require manually prepared data to train a classifier to determine the best or to rank the candidates. The effectiveness of such machine classifiers depends heavily on the amount of training data. Since sufficient training data are difficult to prepare, a set of hand-crafted rules are devised instead: (1) From the candidate list, find the candidate with highest similarity, called X, and the candidate with largest length ratio, called Y.
(i) If X =Y, then output X.
(iii) Remove the candidate just output from the list.

Performance Evaluation
Based on the above steps, the summary candidates of length limit 45 for the third story in Table 1 are exactly the three in Table 2. The (ratio, similarity) values for the candidates are (0.7556, 0.7351), (1.0, 0.7757), and (0.8444, 0.6718), respectively.
Step 3 sorts Candidates 1, 2, and 3 into 2, 3, and 1 in decreasing order of rank. As to the quality of the candidates, Candidate 2 with rank 1 is correct and coherent in meaning and is perfect in length. Candidate 3 is fair in Chinese expressions. It would become better if the word: "他們" ("they") in the beginning of the second clause were deleted. Candidate 1 is also correct and coherent. It carries more interesting content than Candidate 2, but it is shorter in length.
To further evaluate the above method, two sets of news stories were used. One set contained 40 Chinese news stories, which were real-time news (short stories updated every 30 minutes) from China Times 2 between August and September in 2003. Some of the stories, together with the above examples, were used to tune the parameters mentioned in the previous section. Therefore, this group of stories can be considered an inside testing set. The other set contains 75 normal stories, also from China Times between April 4 and 12 in 2009. The parameters and programs set for the inside testing set were used for these recent stories. Thus, they can be considered our outside testing set. Table 3 shows some statistics about these stories in the two sets.

Average Statistics
For each story in both sets, summary candidates were generated and ranked by the proposed method. A human summarizer chose a candidate that he/she thought to be the best among the candidates. The chosen one was then labeled in terms of its quality with one of the three tags: G (good), F (fair), or B (bad) if it was correct and coherent, correct with some readability, or unacceptable, respectively. The inside testing set was evaluated by one human summarizer, while the outside testing set was evaluated by 15 people each for 5 stories. All of the evaluators majored in library science, thus, have some sense of knowledge for manual summarization. Table 4 shows the results for the inside testing set, where for each news story the title and the best candidates for length limit 45 and 69 are shown, respectively. The actual lengths of the best candidates are shown in the second column. In the fourth column, with a *, the number of body sentences in that story is shown in the title row, while the rank of the chosen candidate is listed besides the candidate. The last column indicates the manual judgment of the machine-generated summary.  Table 5 summarizes the data shown in Table 4. As can be seen, of the 40 stories, 65.0% or 62.5% of the first candidates suggested by the method for the length limit 45 and 69, respectively, were judged good. If users were able to choose from all the suggested candidates, 80% or 75% of the summaries could be obtained from a machine without manual editing. Only about 12.5% or 10% of the stories yielded summaries that were unacceptable. The best candidates that are unacceptable (9 cases in total in news ID 4, 5, 8, 15, 17, 32, 33, and 40) contain undesired conjunctions that break the coherence and/or readability (4 cases in 4, 5, 8, 33), clauses that duplicate the headline strings (2 cases in 17 and 32), or were nothing but the headline itself, which means that no candidates could be generated under the required length limit (3 cases in 15 and 40). The suitability of conjunctions for direct concatenation is difficult to judge, because some of them are helpful and some are not. The cases of headline duplication can be eliminated by duplication detection before concatenation. As to those candidates that contain only headlines, the clauses can be broken into smaller structures, such as phrases, for re-combination. This, however, would be a more difficult problem that would require more language analysis. Table 6 summarizes the results for the outside testing set. As can be seen, the percentages of the first suggested candidates that were judged good decrease from 65% and 62.5% to 18.7% and 33.3%, respectively, for the length limit 45 and 69. The percentages that were judged good regardless of the rank position decreased from 80% to 53.3% for the length limit 45 and from 75% to 70.7% for the length limit 69, showing that the shorter the length limit, the less stable the method in performance. A large portion of the percentage moves to those that were judged fair. This decrease in performance may due to the greater number of body sentences and the larger number of evaluators for the outside testing set. As more candidates (and evaluators) exist for selection, less coincidence exists for the same choice (and judgment) results. The only consistent result (compared to the inside testing set) is that those best candidates that were judged bad are still rare (less than 10%). This shows that the heuristic: "concatenating the last clauses of the body sentence with the headline" seems to work for Chinese news in this application.

Discussion
The fact that the proposed method works for some stories is due to the characteristics of Chinese news. They tell stories in a successive sequence. Very few grammatical inversions within sentences and clauses are used. Chinese words have virtually no morphological variations. The clauses, especially at the rear part of a sentence, are sometimes quite independent of the front part. Headlines are given in a compact form to cover as many important facets as possible, such as who, what, where, when, why, and how. All of these characteristics make clause recombination a choice for summary generation. With this

News Brief Services on Cellular Phones
heuristic strategy, the remaining work is to evaluate their fitness as summaries and rank them in a correct sense. For the news stories we tested, the proposed method applies to most of them with success. Nonetheless, for stories not of this type, such as editorials, commentaries, and lists of events, items, or prices, this method may fail. For the stories whose headlines are more eye-catching rather than informative, such that most content words do not appear in the headlines, this method may fail as well.

Conclusions
The proposed method recombines snippets of news without modifying them. A direct advantage is that other synchronized media such as images, speech, or video of the same story can maintain synchronization with ease when they are summarized as well (like those in (ANSES, n.d.)), because the positions of where to cut and paste are known during the generation of the summary candidates. Thus, to achieve speech or video segmentation and summarization for similar services, one can use their synchronized texts based on this method.
Other practical advantages of this computer-assisted summarization include the ease of maintaining summary quality regardless of the experience of human summarizers and the reduction in the cost and time to train novices for this kind of services.
Evaluation of the quality of auto-generated summaries requires human judgment and is, thus, expensive and time-consuming for large-scale or multiple-run evaluation. To allow automatic evaluation using the methodology like those used in machine translation (Papineni, Roukos, Ward, & Zhu, 2002;Doddington, 2002), a number of test collections need to be created. Our past research projects in Chinese OCR text retrieval and Chinese document classification have results in two corresponding test collections for free use 2004). We hope that we can also release a Chinese collection for evaluating automatic summarization in the future.