NO329297B1

NO329297B1 - Extraction of text content from documents on the World Wide Web

Info

Publication number: NO329297B1
Application number: NO20091412A
Authority: NO
Inventors: Eric Moore
Original assignee: Microsoft Int Holdings B V
Priority date: 2009-04-07
Filing date: 2009-04-07
Publication date: 2010-09-27
Also published as: NO20091412A

Abstract

I en fremgangsmåte for å identifisere og ekstrahere tekstinnhold i et dokument (webside) på World Wide Web (WWW), hvor dokumentet omfatter ulike typer innhold, avbildes dokumentet i ikke-overlappende deler og en lenketetthet for hver del ("chunk") beregnes, hvoretter ikke-lenket tekstinnhold i dokumentet kan ekstraheres.In a method for identifying and extracting textual content in a document (web page) on the World Wide Web (WWW), where the document comprises different types of content, the document is imaged in non-overlapping sections and a link density for each section ("chunk") is calculated, after which non-linked text content in the document can be extracted.

Description

OPPFINNELSENS OMRÅDE FIELD OF THE INVENTION

Den foreliggende oppfinnelsen vedrører en fremgangsmåte for å identifisere og ekstrahere tekstinnhold i et dokument (webside) på verdensveven (WWW- World Wide Web), hvor dokumentet omfatter ulike typer innhold inkludert tekst, audio og video samt navigatorer og tilhørende lenker. The present invention relates to a method for identifying and extracting text content in a document (web page) on the World Wide Web (WWW - World Wide Web), where the document includes various types of content including text, audio and video as well as navigators and associated links.

INNLEDNING INTRODUCTION

Dokumenter på WWW-sidene omfatter ulike typer materiale og har et innhold som kan bestå av tekst, men også bilder inkludert video og audio (lydspor), samt rent audioinnhold. I tillegg omfatter websider også navigatorer og ulike interaktive trekk, f .eks. annonser, som er ganske vanlig forekommende på nyere steder på www. For eksempel inneholder en typisk nyhetsside på weben i gjennomsnitt en tredjedel tekstinnhold, en annen tredjedel navigasjonslenker til andre dokumenter eller artikler nyhetsstedene og den resterende tredjedelen eller mer typisk interaktive annonser. Som resultat av dette er webdokumentene overstrødd med trivi-elle trekk som omfatter et stort antall lenkesom representerer støy for brukeren som er interessert i mer verdifulle deler av webinnholdet, for eksempel et rent nyhetsstykke. Documents on the WWW pages include various types of material and have content that can consist of text, but also images including video and audio (sound track), as well as pure audio content. In addition, websites also include navigators and various interactive features, e.g. advertisements, which are quite common in recent places on www. For example, a typical news page on the web contains on average one third text content, another third navigational links to other documents or articles the news sites and the remaining third or more typically interactive advertisements. As a result, the web documents are sprinkled with trivial features that include a large number of links that represent noise to the user who is interested in more valuable parts of the web content, for example a pure news piece.

Verdifulle websider, så som nyhetsartikler publisert av mediaselskap (f.eks. CNN), består typisk av tre hoveddeler, nemlig artikkelens tekstinnhold inkludert tittel, signatur, publiseringsdato og artikkelinnhold; navigerings- og informasjonslenker fra siden til andre deler av nettstedet eller beslektet innhold; og interaktive annonser. Disse seksjonene kan variere og varierer vilt fra sted til sted og til og med fra side til side. Valuable web pages, such as news articles published by media companies (eg CNN), typically consist of three main parts, namely the textual content of the article including title, signature, publication date and article content; navigational and informational links from the Site to other parts of the Site or related content; and interactive ads. These sections can and do vary wildly from site to site and even from site to site.

KJENT TEKNIKK PRIOR ART

Lesere (menneskelige) er blitt flinke til å finne og fokusere på artikkelinnhold, mens annet rot ignoreres (i det minste periodevis). Programvaresystemer har imidlertid måttet baseres på et utvalg menneskelige (redaksjonelle) og nettsteds-spesifikke (rå kraft) tilnærminger for å oppnå samme effekt. For eksempel kan pro-gramvare se etter bestemte spor i HTML, CSS eller endog utviklerkommentarer for å forsøke å identifisere begynnelsen og slutten av en artikkel, eller de kan av-henge av en person som manuelt identifiserer artikler. De beste slike løsninger krever kanskje en times konfigurasjon for hvert sted før det er mulig med ekstrahering på hele stedet. Disse tilnærmingene kan være nye, men de er ganske enkelt ikke skalerbare. Å implementere artikkelekstrahering på et par tusen nyhetsste-der ville antakelig ta mann-måneder med arbeid. Disse løsningene er også grunnleggende ustabile i det de kan behøve rekonfigurasjon selv etter en mindre end-ring av nettstedets oppsett. Readers (human) have become good at finding and focusing on article content, while ignoring other clutter (at least periodically). However, software systems have had to rely on a variety of human (editorial) and site-specific (raw power) approaches to achieve the same effect. For example, software may look for specific traces in HTML, CSS, or even developer comments to attempt to identify the beginning and end of an article, or they may depend on a person manually identifying articles. The best such solutions may require an hour of configuration for each site before site-wide extraction is possible. These approaches may be novel, but they are simply not scalable. Implementing article extraction on a few thousand news sites would probably take man-months of work. These solutions are also fundamentally unstable in that they may need reconfiguration even after a minor change to the site's layout.

En annen tilnærming til dette problemet har vært å implementere lingvistisk (språk) analyse som prøver å identifiseres hva ulike deler av en webside handler om, og således identifisere artikkelinnholdet. Another approach to this problem has been to implement linguistic (language) analysis which tries to identify what different parts of a web page are about, and thus identify the article content.

Konkrete tilfeller av kjent teknikk blir nå mer detaljert beskrevet. Concrete cases of prior art are now described in more detail.

US patentnummer 6 665 836, "Method for managing information on an information net" (Wymblatt et al., overdratt til Siemens Corporate Research, Inc.) beskriver en fremgangsmåte for å håndtere informasjon i et informasjonsnett, så som WWW. Fremgangsmåten omfatter trinn for å ekstrahere utvalgte dokumentegenskaper fra et strukturert dokument, og inkluderer ekstrahering av egenskaper som angår lenketetthet. En trekkvektor som representerer disse egenskapene blir så funnet og presentert. Trekkvektoren kan så brukes til å danne en såkalt karikatur-representasjon som er en svært forenklet avbilding av det faktiske trekket, men likevel lett gjenkjennelig. US Patent Number 6,665,836, "Method for managing information on an information net" (Wymblatt et al., assigned to Siemens Corporate Research, Inc.) describes a method for managing information in an information network, such as the WWW. The method comprises the steps of extracting selected document properties from a structured document, and includes extracting properties relating to link density. A feature vector representing these properties is then found and presented. The feature vector can then be used to form a so-called caricature representation which is a very simplified depiction of the actual feature, but still easily recognisable.

US patentnummer 6 741 986, "Method and system for performing information extraction and quality control for a knowledgebase" (Cho et al., overdratt til Ingenuity Systems, Inc.) beskriver hvordan informasjon blir ekstrahert fra flere artikler på en distribuert måte, og så lagret i et informasjonslager. Fremgangsmåten er basert på en seleksjons og identifikasjonsprosedyre for å bestemme mengden av artikler som informasjon skal ekstraheres fra, og identifiserer også flere informasjonsekstraktorer. Fremgangsmåten synes å ha en viss sammenheng med automatisert sammendragning av artikler, og tilveiebringer således tilsyne-latende datamaskinbehandling av mentalt baserte prosesser slik de har vært utført i dekader. US patent number 6,741,986, "Method and system for performing information extraction and quality control for a knowledgebase" (Cho et al., assigned to Ingenuity Systems, Inc.) describes how information is extracted from multiple articles in a distributed manner, and then stored in an information store. The method is based on a selection and identification procedure to determine the amount of articles from which information is to be extracted, and also identifies several information extractors. The procedure seems to have some connection with automated summarization of articles, and thus provides apparent computer processing of mentally based processes as they have been carried out for decades.

US patentnummer 6 924 828, "Method and apparatus for improved information representation" (Hirsch, overdratt til Surfnotes) synes i en viss grad å vedrøre et lignende problem som det foregående dokumentet, ved at det er basert på indeksering, kategorisering og sammentrekning av data fra tekst eller andre dokumenter. Målet er å tilveiebringe et raskt flersiders webnavigasjonssystem, og et særskilt mål synes å være å organisere og fremvise informasjon for presentasjon på innretninger hvor skjermstørrelsen og fremvisningsressursene er begrensede. US Patent No. 6,924,828, "Method and apparatus for improved information representation" (Hirsch, assigned to Surfnotes) appears to somewhat address a similar problem to the preceding document, in that it is based on indexing, categorization and contraction of data from text or other documents. The goal is to provide a fast multi-page web navigation system, and a particular goal seems to be to organize and display information for presentation on devices where screen size and display resources are limited.

US patentnummer 7 047 033, "Methods and apparatus for analyzing, processing and formatting network information such as web-pages" (Wyler, overdratt til Infogin Ltd) beskriver en fremgangsmåte for å behandle informasjon mottatt av en trådløs innretning over et datamaskinnettverk og omfatter å motta informasjon fra minst en informasjonskilde over nettverket. Minst noe av informasjonen blir analysert, og noen av resultatene fra analysen blir brukt til å fremskaffe informasjon i en form egnet for fremvisning til en bruker. Målet er å tilveiebringe en fremgangsmåte hvorved informasjon fra f.eks. WWW i form av nedlastede dokumenter kan bli behandlet for å gi et format egnet fro fremvisning på trådløse innretninger som mobiltelefoner med begrenset skjermplass. Beskrivelsen av dette dokumentet er derfor også beslektet med søknadsgjenstandene i de ovennevnte dokumentene. US patent number 7,047,033, "Methods and apparatus for analyzing, processing and formatting network information such as web-pages" (Wyler, assigned to Infogin Ltd) describes a method for processing information received by a wireless device over a computer network and includes receive information from at least one information source over the network. At least some of the information is analyzed, and some of the results from the analysis are used to provide information in a form suitable for presentation to a user. The aim is to provide a method whereby information from e.g. WWW in the form of downloaded documents can be processed to provide a format suitable for display on wireless devices such as mobile phones with limited screen space. The description of this document is therefore also related to the application objects in the above-mentioned documents.

Endelig beskriver allment tilgjengelige US patentsøknad nummer 2003/0046318, "Reorganizing content of an electronic document" (Schohn et al.), en fremgangsmåte hvor et elektronisk dokument mottas og representerer seriedata innehold-ende dokumentinnholdet og definerer en rekkefølge for visning av de respektive delene av innholdet. Det elektroniske dokumentets seriedata blir analysert, og reorganiseringsinformasjon blir generert til bruk ved levering av deler av innholdet, i det reorganisering for eksempel muliggjør fremvisning i en annen rekkefølge enn rekkefølgen definert av seriedata. Innhold synes å bli klassifisert etter en tre basert prosedyre, og deretter blir analysert reorganiseringsinformasjon generert slik at en automatisk omdirigering fra den første delen av innholdet til etterfølgende deler av innholdet kan utføres når dokumentet er åpent for betraktning. En hyperlink kan våre til stede i reorganiseringsinformasjonen og fremvises i begynnelsen av det åpne dokumentet, men som peker til en del av innholdet som fremkommer mye senere i den opprinnelige rekkefølgen. Bruken av hyperlink hevdes å være be-stemt av avstand, dvs avhengig av avstanden mellom hyperlenken i det åpnede dokumentet og stedet hyperlenken peker til. Finally, publicly available US patent application number 2003/0046318, "Reorganizing content of an electronic document" (Schohn et al.), describes a method where an electronic document is received and represents serial data containing the document content and defines an order for displaying the respective parts of the content. The electronic document's serial data is analyzed, and reorganization information is generated for use when delivering parts of the content, in that reorganization, for example, enables presentation in a different order than the order defined by serial data. Content appears to be classified according to a tree-based procedure, and then analyzed reorganization information is generated so that an automatic redirection from the first part of the content to subsequent parts of the content can be performed when the document is open for viewing. A hyperlink can be present in the reorganization information and displayed at the beginning of the open document, but which points to a part of the content that appears much later in the original order. The use of hyperlinks is claimed to be determined by distance, ie depending on the distance between the hyperlink in the opened document and the place the hyperlink points to.

Som det vil fremgå av drøftelsen ovenfor av patentdokumenter fra kjent teknikk, synes ingen av dem å dreie seg spesifikt om å tilveiebringe en effektiv og rasjonell fremgangsmåte for å ekstrahere tekstlig innhold. Selv om de i noen grad angår klassifisering av innhold i dokumenter, synes dette hovedsakelig å bli utført for presentasjons- og fremvisningsformål når beskrankninger er påtrykt av begrensede ressurser så som skjermplass på brukerinnretninger. As will be apparent from the above discussion of prior art patent documents, none of them appear specifically to provide an efficient and rational method for extracting textual content. Although to some extent they concern the classification of content in documents, this seems to be mainly done for presentation and display purposes when restrictions are imposed by limited resources such as screen space on user devices.

FORMÅL MED OPPFINNELSEN OBJECTS OF THE INVENTION

I lys av manglene ved den ovennevnte kjente teknikk, er det et hovedformål med den foreliggende oppfinnelsen å identifisere og ekstrahere tekstlig innhold i dokumenter på WWW eller websider uten menneskelig innblanding. In light of the shortcomings of the above-mentioned prior art, it is a main purpose of the present invention to identify and extract textual content in documents on the WWW or web pages without human intervention.

Et annet formål med den foreliggende oppfinnelsen er å identifisere tekstlig innhold i en webside uavhengig av websidens språk eller layout. Another purpose of the present invention is to identify textual content in a web page regardless of the web page's language or layout.

Et siste formål med den foreliggende oppfinnelsen er å tilveiebringe et kriterion for høypålitelig ekstrahering av tekstlig innhold på en webside og å sikre at resten av websidens innhold ekskluderes. A final object of the present invention is to provide a criterion for highly reliable extraction of textual content on a web page and to ensure that the rest of the web page's content is excluded.

OPPSUMMERING AV OPPFINNELSEN SUMMARY OF THE INVENTION

Formålene ovenfor, så vel som ytterligere trekk og fordeler, realiseres med en fremgangsmåte i følge den foreliggende oppfinnelsen, som er karakterisert ved trinn for å avbilde dokumentet til bestanddeler eller seksjoner kalt chunker, idet hver chunk identifiseres av et HTML-element så som <p> eller <dib>, å beregne forholdet mellom lenket og ikke-lenket innhold som en lenketetthet for chunken, å generere en graf av sekvensen av chunkenes posisjoner i dokumentet mot den beregnede lenketettheten, og å ekstrahere et grunnleggende ikke-lenket tekstlig innhold i dokumentet som chunkene som har de totalt laveste lenketetthetene. The above objectives, as well as further features and advantages, are realized with a method according to the present invention, which is characterized by steps to map the document into components or sections called chunks, each chunk being identified by an HTML element such as <p > or <dib>, to calculate the ratio of linked to unlinked content as a link density for the chunk, to generate a graph of the sequence of the chunks' positions in the document against the calculated link density, and to extract a basic unlinked textual content of the document as the chunks that have the overall lowest link densities.

Ytterligere trekk og fordeler skal fremgå av de vedføyde uselvstendige patentkrav. Further features and advantages shall be apparent from the attached non-independent patent claims.

Oppfinnelsen skal forstås bedre med henvisning til den følgende drøfting av dens sentrale trekk, så vel som eksempler på utførelsesformer av den, og med henvisning til de vedføyde figurene, hvor: The invention will be better understood with reference to the following discussion of its central features, as well as examples of embodiments thereof, and with reference to the attached figures, in which:

fig. 1 viser en typisk webside fra et nyhetssted, fig. 1 shows a typical web page from a news site,

fig..2a en graf som gir en lenketetthet av dokumentseksjoner som en funksjon av en sekvensiell posisjon av dem i dokumentet, og med en stor sammenhengende region med lav lenketetthet, fig..2a a graph giving a link density of document sections as a function of a sequential position of them in the document, and with a large contiguous region of low link density,

fig. 2b en graf som gir en lenketetthet tilsvarende fig 2a, men med mange mindre regioner med lav lenketetthet adskilt av platåer med høy lenketetthet, fig. 2b a graph giving a link density similar to Fig. 2a, but with many smaller regions of low link density separated by plateaus of high link density,

fig. 3 skjematisk den visuelle organiseringen av typiske websider, fig. 3 schematically the visual organization of typical web pages,

figurene 4a-4c skjematiske trinn i innføringsdelen av fremgangsmåten i følge den foreliggende oppfinnelsen, figures 4a-4c schematic steps in the introduction part of the method according to the present invention,

figurene 5a-5e skjematiske trinn i selve lenketetthetsanalysen slik den utføres i fremgangsmåten i følge den foreliggende oppfinnelsen, figures 5a-5e schematic steps in the link density analysis itself as it is carried out in the method according to the present invention,

figurene 6a og 6b trinn i ekstraheringsdelen av fremgangsmåten i følge den foreliggende oppfinnelsen Figures 6a and 6b show steps in the extraction part of the method according to the present invention

fig. 7 en annen typisk webside som skal underkastes en lenketetthetsanalyse, fig. 7 another typical web page to be subjected to a link density analysis,

fig. 8 en type stolpediagram over klassifiserte sidechunker og statistisk bruk for klassifisering, og fig. 8 a type of bar chart of classified page chunks and statistical use for classification, and

fig. 9 det identifiserte og ekstraherte artikkelinnholdet fra siden i fig. 7. fig. 9 the identified and extracted article content from the page in fig. 7.

DETALJERT BESKRIVELSE DETAILED DESCRIPTION

Som bemerket i den foregående seksjonen, er websider så som nyhetsartikler typisk sammensatt av tekstinnhold, navigasjonslenker og annonser. Faktisk er annonser grunnleggende navigasjonsorienterte. De er lenker. Tekstinnhold kan ha lenker i seg, men navigatorer og annonselenker er typisk intet mer enn lenker. Dette er nøkkelen til å løse problemet med å ekstrahere kun tekstlig innhold. As noted in the previous section, web pages such as news articles are typically composed of textual content, navigational links, and advertisements. In fact, ads are fundamentally navigation oriented. They are links. Text content can have links in it, but navigators and ad links are typically nothing more than links. This is the key to solving the problem of extracting textual content only.

For eksempel viser fig. 1 en typisk webside som kan lastes ned fra webstedet CNN.com, som er et velkjent nyhetssted på WWW. Det innses at denne websiden omfatter et utvalg innholdstyper, av hvilke rent tekstlig innhold, dvs selve nyhetsmeldingen, i fig. 1 er tydelig innrammet for å markere den over de resterende delene av denne siden. Det skal innses at resten av siden omfatter navigatorer for søk og tjenester. Slik det fremstår til høyre for det tekstlige innholdet, er bilder øyensynlig inkludert i form av en lysbildefremvisning, og lenker til andre webdoku-menter på det samme nyhetsstedet finnes nedenfor bildet. Videre er det lenker til andre tjenester, inkludert jobbtjenester og typiske som finnes i form av annonser, f.eks. fra en tjeneste så som et karrierebyggerkurs. Det er også lenker til finansielle tjenester og øyensynlig lenker som kan betraktes som skjult annonsering for tjenester eller tjenestetilbud, i dette tilfellet lånetilbud og finansielle kalkulatorer. Som den ses, er den en typisk webside overstrødd med trekk i tillegg til dens fulle tekstlige innhold, og ved et overflatisk blikk på dokumentet ses at tekstlig innhold i dette tilfellet omfatter omtrent en tredjedel eller mindre av dokumentet. For example, fig. 1 a typical web page that can be downloaded from the CNN.com website, which is a well-known news site on the WWW. It is realized that this website comprises a selection of content types, of which purely textual content, i.e. the news release itself, in fig. 1 is clearly framed to mark it above the remaining parts of this page. It should be understood that the rest of the page includes navigators for searches and services. As it appears to the right of the textual content, images are apparently included in the form of a slide show, and links to other web documents on the same news site can be found below the image. Furthermore, there are links to other services, including job services and typical ones found in the form of advertisements, e.g. from a service such as a career building course. There are also links to financial services and apparently links that can be considered as hidden advertising for services or service offers, in this case loan offers and financial calculators. As seen, it is a typical web page sprinkled with features in addition to its full textual content, and a cursory glance at the document shows that textual content in this case comprises about a third or less of the document.

Websider er kodet i HTML (Hype Text Markup Language). HTML-sider kan omfatte andre teknologier så som et skriptspråk som javaskript, og anvende format-teringsstiler gjennom CSS (Cascading Style Sheets). Tekstinnholdet er imidlertid tilslutt alltid lagt direkte inn i HTML-koden. Hvis HTMLs innebyggede formatter-ingsegenskaper ignoreres kommer tekst kun i to varianter: ren (ulenket) eller hyperlenket gjennom ankermerket <a>. Tekst er normalt organisert i seksjoner, mest slik at den kan plasseres på en side og/eller formatteres via CSS. Siden formatteringen for en seksjon typisk vil være unik, er hver seksjon i HTML typisk unik. Web pages are coded in HTML (Hype Text Markup Language). HTML pages can include other technologies such as a scripting language such as javascript, and apply formatting styles through CSS (Cascading Style Sheets). In the end, however, the text content is always entered directly into the HTML code. If HTML's built-in formatting properties are ignored, text comes in only two varieties: plain (unlinked) or hyperlinked through the <a> anchor tag. Text is normally organized into sections, mostly so that it can be placed on a page and/or formatted via CSS. Since the formatting for a section will typically be unique, each section in HTML is typically unique.

For å identifisere en artikkel eller tekstlig innhold ved hjelp av den foreliggende oppfinnelsen må derfor de følgende trinn utføres: • Avbilde websiden sekvensielt til adskilte chunker, hvor hver chunk er en seksjon identifisert av et grunnleggende HTML-element så som <p> eller <div> In order to identify an article or textual content using the present invention, the following steps must therefore be performed: • Sequentially map the web page into separate chunks, where each chunk is a section identified by a basic HTML element such as <p> or <div >

• Beregne for hver chunk forholdet mellom lenket og ulenket (ren) tekst • Calculate for each chunk the ratio between linked and unlinked (clean) text

- dette forholdet kalles chunkens "lenketetthet". - this ratio is called the "link density" of the chunk.

• Lage en graf over chunkplasseringen (i rekkefølge) mot linktettheten for chunken. En funksjon som vist i fig. 2a eller fig. 2b vil fremkomme. • Create a graph of the chunk location (in order) against the link density for the chunk. A function as shown in fig. 2a or fig. 2b will appear.

I motstetning til fig. 2a, viser grafen i fig. 2b flere små regioner med lav lenketetthet adskilt av platåregioner med høy lenketetthet. Dette er svært trolig en såkalt nav-side som omfatter innledninger eller toppdeler av et antall artikler adskilt av navigatorer, annonser og andre lenkede enheter. In contrast to fig. 2a, shows the graph in fig. 2b several small regions of low link density separated by plateau regions of high link density. This is very likely a so-called nav page comprising introductions or headers of a number of articles separated by navigators, advertisements and other linked units.

Hvis et mønster av funksjonen som den som vises i fig. 2a overveies, ses at en sammenhengende og stor mengde chunker i dokumentet er kjennetegnet ved at den har en vesentlig lav total lenketetthet, og som vist er de markert omsluttet av en bred kontinuerlig kontur. Siden lenketettheten til chunker med tekstlig innhold er lav eller til og med null, kan denne sekvensen av chunker med høy konfidens identifiseres som tekstlig, f.eks. en artikkel, og ekstraheres. Områdene med høy lenketetthet i fig. 2a tolkes som navigatorer og annonser. If a pattern of the function such as that shown in fig. 2a is considered, it is seen that a continuous and large amount of chunks in the document is characterized by having a significantly low total link density, and as shown, they are markedly enclosed by a broad continuous contour. Since the link density of chunks with textual content is low or even zero, this sequence of chunks can be identified as textual with high confidence, e.g. an article, and is extracted. The areas with high link density in fig. 2a are interpreted as navigators and advertisements.

For å optimalisere ekstraheringen av tekstlig innhold, er det mulig på grunnlag av den beregnede lenketettheten som vises i fig. 2a å etablere en lenketetthetsterskel for å sikre ekstrahering av alt tekstlig innhold med høy pålitelighet. Avvikene til lenketettheten for de lenkede eller svært lenkede chunkene i dokumentet er til-synelatende svært signifikant. Videre, hvis fig. 2a sammenholdes med websiden i fig. 1, vises at en inndeling av dette dokumentet i chunker fra begynnelse til slutt vil resultere i en sammenhengende seksjon av chunkene i dokumentet som svarer til kun tekstlig og ikke-lenket innhold, dvs meldingen som vises markert med en kraftig ramme i fig. 1. Denne delen vil tilsvare delen av grafen i fig. 2a som har de laveste totale lenketetthetene. Det ses også at en navigatordel av dokumentet i fig. 1, for eksempel til høyre for nyhetsmeldingen, generelt vil ha en svært høy lenketetthet. Det samme vil være tilfellet med den høyre delen av websiden i fig. 1, hvor lenketettheten øker noe og stødig, avhengig av det faktiske innholdet, for eksempel lenker til andre websider på nettstedet, eller nærmer seg en svært høy lenketetthet i deler av websiden som omfatter lenker til annonser og tilbudte tjenester, slik som vil være tilfellet på kolonnen lengst til høyre på websiden i fig. 1. In order to optimize the extraction of textual content, it is possible on the basis of the calculated link density shown in fig. 2a to establish a link density threshold to ensure extraction of all textual content with high reliability. The deviations of the link density for the linked or highly linked chunks in the document are apparently very significant. Furthermore, if fig. 2a is compared with the web page in fig. 1, it is shown that a division of this document into chunks from beginning to end will result in a continuous section of the chunks in the document which corresponds to only textual and non-linked content, i.e. the message shown marked with a heavy frame in fig. 1. This part will correspond to the part of the graph in fig. 2a which have the lowest total link densities. It can also be seen that a navigator part of the document in fig. 1, for example to the right of the news message, will generally have a very high link density. The same will be the case with the right part of the web page in fig. 1, where the link density increases somewhat and steadily, depending on the actual content, for example links to other web pages on the website, or approaches a very high link density in parts of the website that include links to advertisements and services offered, as will be the case on the rightmost column on the web page in fig. 1.

Fremgangsmåten i den foreliggende oppfinnelsen kalles i det følgende lenketetthetsanalyse eller LDA (Link Density Analysis) og gjør essensielt to ting, nemlig å ekstrahere HTML for en side, hvor HTML selvsagt tilsvarer dens unike innhold, og LDA kan så brukes til å klassifisere siden som artikkel, blogg eller nav. For å ut-føre fremgangsmåten i følge den foreliggende oppfinnelsen, nemlig LDA, kan fremgangsmåten betraktes som omfattende en lenketetthetsanalysator, og lenke-tetthetsanalysatoren vil blant annet også omfatte algoritmen for å beregne en naturlig lenketetthet for en side. The method in the present invention is hereinafter called link density analysis or LDA (Link Density Analysis) and essentially does two things, namely extracting the HTML for a page, where the HTML of course corresponds to its unique content, and LDA can then be used to classify the page as an article , blog or nav. In order to carry out the method according to the present invention, namely LDA, the method can be considered as comprising a link density analyser, and the link density analyzer will, among other things, also include the algorithm for calculating a natural link density for a page.

Den visuelle organiseringen av det store flertall av websider er skjematisk skissert The visual organization of the vast majority of web pages is schematically outlined

i fig. 3, dokumentobjekt-modellen (DOM) som ligger til grunn for sideimplementa-sjonen er tilføyd. Det er en beholdernode - en <div>, <td>, <table> ved "roten" av hvert visuelle eller strukturelle element. Ved indeksering for søk, er det ønskelig å ekstrahere "artikkelen" og utelukket "navet". Problemet nå er å finne "artikkel"-noden. Til dette kunne et egnet verktøy for strukturanalyse blitt anvendt, og gjort det mulig å identifisere fra sidens layout en beholdernode deklarativt med regler. LDA-tilnærmingen i følge fremgangsmåten i den foreliggende oppfinnelsen er å identifisere lavnivånoder som de nærmeste forløperne til klynger av tekst og lenketekst, deretter å skåre disse nodene og så å slå sammen disse relevante nodene til aggregater som er ekvivalente med beholdernoder for visuelle elementer. De deduserte aggregatene har målbare attributter - for eksempel en prosentandel tekst mot lenket tekst - som kan brukes til pålitelig identifisering av innholdet på en side i forhold til andre elementer på siden. De samme attributtene kan brukes til å klassifisere sidens mønster som et "mønster" for siden som helhet, nemlig som Artikkel, Blogg eller Nav. LDAen blir nå skissert trinn for trinn i henhold til det følg-ende skjema: in fig. 3, the document object model (DOM) underlying the page implementation has been added. There is a container node - a <div>, <td>, <table> at the "root" of each visual or structural element. When indexing for search, it is desirable to extract the "article" and exclude the "hub". The problem now is to find the "article" node. For this, a suitable tool for structural analysis could have been used, making it possible to identify a container node declaratively with rules from the page's layout. The LDA approach according to the method of the present invention is to identify low-level nodes as the closest precursors to clusters of text and link text, then to score these nodes and then to merge these relevant nodes into aggregates equivalent to container nodes for visual elements. The inferred aggregates have measurable attributes—such as a percentage of text versus linked text—that can be used to reliably identify the content of a page relative to other elements on the page. The same attributes can be used to classify the page's pattern as a "pattern" for the page as a whole, namely as Article, Blog or Hub. The LDA is now outlined step by step according to the following scheme:

LDA-oversikt LDA overview

Innføring Introduction

Inndel HTML i LDA "chunker" Split HTML into LDA "chunker"

Skår chunker Cut chunks

Merk relevante chunker Mark relevant chunks

Analyse Analysis

Samle chunker til et tre av klumper Collect chunks into a tree of chunks

Aggreger klumpløv Aggregate lump leaves

Gjør treet flatere ved å splitte grenklumper Make the tree flatter by splitting clumps of branches

Analyser fordelingen av klumper Analyze the distribution of clumps

Klassifiser siden Classify the page

Ekstrakt Extract

Beskjær "artikkel"-chunken Trim the "article" chunk

Vis tekst, artikkel, diagnostiske syn Show text, article, diagnostic views

I det følgende blir hvert trinn i fremgangsmåten i henhold til den foreliggende oppfinnelsen drøftet i større detalj, dvs trinnene i LDA nummerert i rekkefølge, og ved slutten av beskrivelsen er hvert trinn formalisert i pseudokode. In the following, each step in the method according to the present invention is discussed in greater detail, i.e. the steps in LDA are numbered in order, and at the end of the description each step is formalized in pseudocode.

1. Analyse av HTML for å konstruere LDA- modellen 1. Analysis of HTML to construct the LDA model

For å få et visuelt grep om LDA og dens sekvensielle progresjon, kan dokumentet visualiseres skjematisk som i fig. 4a. Noder i LDA-modellen er "Chunker". Chunker omhyller elementer i HTMLs DOM, nemlig tekst og tag-noder. LDA-modellen er et tre. LDA "krever" at den underliggende HTML-analysatoren og DOM er i stand til å identifisere tag-typer, navigere forelder og barnenoder, og gitt node kan fremstilles som en "ren tekst" streng. Dette trinnet kan fremstilles som den følgende pseudokode: To get a visual grasp of LDA and its sequential progression, the document can be visualized schematically as in fig. 4a. Nodes in the LDA model are "Chunkers". Chunkers wrap elements in HTML's DOM, namely text and tag nodes. The LDA model is a tree. LDA "requires" the underlying HTML parser and DOM to be able to identify tag types, navigate parent and child nodes, and given node can be represented as a "plain text" string. This step can be represented as the following pseudocode:

2. Skår 2. Score

Dette trinnet er skjematisk vist i fig. 4b. Løv"chunker" skåres som "innhold" eller "lenke" eller "annet". Hvis prosentandelen lenketekst på en node er > Terskel, er noden en "lenke"node. En oppverrettet rekursjon gjøres for å klassifisere alle grenchunker. Skåring av grenchunker vil omklassifisere avkommet for konsistens i tilfellet hvor for eksempel en barnechunk er klassifisert som "lenke", men ordan-tallet for denne chunken er mindre enn en terskelandel av den "innhold"-skårede grenchunken som inneholder den. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 4b. Leaf "chunker" is scored as "content" or "link" or "other". If the percentage of link text on a node is > Threshold, the node is a "link" node. An upward recursion is done to classify all branch chunks. Scoring branch chunks will reclassify the offspring for consistency in the case where, for example, a child chunk is classified as "link", but the ordan number for this chunk is less than a threshold proportion of the "content" scored branch chunk that contains it. This step can be represented as the following pseudocode:

3. Marker relevante chunker 3. Mark relevant chunks

Dette trinnet er skjematisk vist i fig. 4c. Den relevante beholderchunken (bestefor-elder eller oldeforelder) for hver tekstnode blir funnet. Dette kan formelt fremstilles med et berømt litterært eksempel This step is schematically shown in fig. 4c. The relevant container chunk (grandparent or great-grandparent) for each text node is found. This can be formally illustrated with a famous literary example

Merkene <div> eller <td> er "relevante". "Relevante chunker" vil ha en tendens til å tilsvare beholdere for layouts. Grenchunker blir markert som forfedre til relevante chunker. Markeringstrinnet kan gis som den følgende pseudokode: The <div> or <td> tags are "relevant". "Relevant chunks" will tend to correspond to containers for layouts. Branch chunks are marked as ancestors of relevant chunks. The marking step can be given as the following pseudocode:

Trinnene 1-3 ovenfor tilsvarer innføringsdelen av fremgangsmåten i følge den foreliggende oppfinnelsen. Steps 1-3 above correspond to the introduction part of the method according to the present invention.

4. Samle chunker til et tre av klumper 4. Collect chunks into a tree of chunks

Dette trinnet er skjematisk vist i fig. 5a. De relevante chunkene kombineres til klumper og relevante chunker grupperes etter den nærmeste "relevante" forfar som klumper. Treet av klumper vil bli rearrangert i det neste trinnet. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 5a. The relevant chunks are combined into chunks and relevant chunks are grouped by the nearest "relevant" ancestor as chunks. The tree of clumps will be rearranged in the next step. This step can be represented as the following pseudocode:

5. Aggreger klumpløv 5. Aggregate clump leaves

Dette trinnet er skjematisk vist i fig. 5b. De "like" klumpene slås sammen. For hver klump (ac), slå (ac) sammen med en annen klump ( ap) hvis ap er en forfar til ac og ap og ac er tilsvarende skåret (innen en terskel), og hvis de respektive chunkene er stort sett homogene. Ideen her er å slå sammen så mange klumper som mulig. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 5b. The "similar" lumps are merged. For each chunk (ac), merge (ac) with another chunk (ap) if ap is an ancestor of ac and ap and ac are similarly cut (within a threshold), and if the respective chunks are largely homogeneous. The idea here is to merge as many lumps as possible. This step can be represented as the following pseudocode:

6. Giør treet flatere ved å splitte grenklumper 6. Make the tree flatter by splitting clumps of branches

Dette trinnet er skjematisk vist i fig. 5c. Hver klump skal splittes hvis klumpen er forfar til en annen klump i treet, og hvis splitten ikke vil øke uorden i treet. Ideen her er å få en flat liste av disjunkte klumper. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 5c. Each lump should be split if the lump is the ancestor of another lump in the tree, and if the split will not increase disorder in the tree. The idea here is to get a flat list of disjoint lumps. This step can be represented as the following pseudocode:

7. Analyser fordelingen av chunker 7. Analyze the distribution of chunks

Dette trinnet er skjematisk vist i fig. 5d. Fra listen over gjenværende klumper bør det tas en grundig titt på tilhørende chunker for å se om en "topp" i antall tekstord på en gitt chunk kan identifiseres i forhold til de andre chunkene. En teksttopp i det masserte treet av klumper tilsvarer "artikkelen" hvis den eksisterer. "Toppen" kan defineres som "maxklumpen". En "maxklump" identifikasjon ivaretar tilfeller med store konsentrasjoner av lenkeord. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 5d. From the list of remaining chunks, a close look at the associated chunks should be taken to see if a "peak" in the number of text words on a given chunk can be identified in relation to the other chunks. A text vertex in the massed tree of lumps corresponds to the "article" if it exists. The "top" can be defined as the "max lump". A "maxklump" identification takes care of cases with large concentrations of link words. This step can be represented as the following pseudocode:

8. Klassifiser siden: Blogg, Nav, Artikkel? 8. Classify the page: Blog, Hub, Article?

Dette trinnet er skjematisk vist i fig. 5e. Regler anvendes for å klassifisere siden. Fordi "lenkechunker" innsatt i "maxchunken" vil bli beskåret, justeres maxchunk-ens skår til å projisere dette. Eksempelregler kan gis: This step is schematically shown in fig. 5e. Rules are used to classify the page. Because "link chunks" inserted into the "maxchunk" will be pruned, the maxchunk's shards are adjusted to project this. Example rules can be given:

• Finnes det en "maxchunk" - (f.eks. "A + B") • Is there a "maxchunk" - (e.g. "A + B")

• Er maxchunken for det meste" innhold" (over en terskel?) —»• Blogg eller • Is the maxchunk mostly "content" (above a threshold?) —»• Blog or

Artikkel Article

• Er de fleste av sidens lenker innefor eller utenfor "maxchunken"? Hvis innenfor kan den klassifiseres som —► Blogg. • Er det en stor andel av "link tekst" på siden? Er "maxchunken" for det meste lenker? Da kan den klassifiseres som —► Nav • Are most of the page's links inside or outside the "maxchunk"? If within it can be classified as —► Blog. • Is there a large proportion of "link text" on the page? Is the "maxchunk" mostly links? Then it can be classified as —► Nav

Dette trinnet kan fremstilles som den følgende pseudokode: This step can be represented as the following pseudocode:

Trinnene 4 til 8 tilsvarer selve lenketetthetsanalysen slik den utføres med fremgangsmåten i følge den foreliggende oppfinnelsen. Den kan også betraktes som en analysator dedikert til å utføre en lenketetthetsanalyse. Steps 4 to 8 correspond to the link density analysis itself as it is carried out with the method according to the present invention. It can also be considered an analyzer dedicated to performing a link density analysis.

9. Beskjær " artikkel- chunkene" 9. Crop the "article chunks"

Dette trinnet er skjematisk vist i fig. 6a. Hvis en side er en Artikkel-side, vil noen innholdschunker (f.eks. "C") som ikke er i "naxchunken" ikke være en del av artikkelen. Disse "chunkene" er markert som "beskåret". Konsentrasjoner av lenke-noder, som tilsvarer "innsatte", beskjæres i henhold til typen av node som inneholder dem, konsentrasjonens skår (praktisk talt alle lenker) og antall noder. Bal-ansen er å fjerne "i andre nyheter" eller "beslektet historie"-innslag uten å fjerne lenkene som er med i artikkeltekst. Dette trinnet kan fremstilles som den følgende pseudokode: This step is schematically shown in fig. 6a. If a page is an Article page, any content chunks (eg "C") that are not in the "naxchunk" will not be part of the article. These "chunks" are marked as "cropped". Concentrations of link nodes, which correspond to "insets", are pruned according to the type of node that contains them, the concentration's shard (practically all links), and the number of nodes. The trick is to remove "in other news" or "related story" features without removing the links that are included in the article text. This step can be represented as the following pseudocode:

10. Komponer tekst, artikkel og diagnostiske syn 10. Compose text, article and diagnostic views

Dette trinnet er skjematisk vist i fig. 6b. Artikkelsynet representerer sidens raffi-nerte BODY for dokumentbehandling. De følgende betingelser skal tilfredsstilles, nemlig: This step is schematically shown in fig. 6b. The article view represents the page's refined BODY for document processing. The following conditions must be satisfied, namely:

For å komponere "teksf-synet blir chunker gjennomløpt ovenfra og ned i samme rekkefølge som HTML-siden fremstilles. Hver relevant ubeskåret løvchunk lagger sin tekst til artikkelen. Sider klassifisert som Nav frembinger ikke noe nyttig "Artikkel"-syn. En HTML-fremstilling av klumpene, chunk DOMen og statistikk opprettes for logging og for LDA webapplikasjonen. Dette trinnet kan fremstilles som den følgende pseudokode: To compose the "textf" view, chunks are traversed from top to bottom in the same order as the HTML page is rendered. Each relevant uncut leaf chunk adds its text to the article. Pages classified as Nav do not produce a useful "Article" view. An HTML rendering of the chunks, the chunk DOM and statistics are created for logging and for the LDA web application.This step can be represented as the following pseudocode:

Trinnene 9 og 10 tilsvarer ekstraktdelen av fremgangsmåten i følge den foreliggende oppfinnelsen. Steps 9 and 10 correspond to the extract part of the method according to the present invention.

En samlet oversikt over fremgangsmåten i følge den foreliggende oppfinnelsen fremstilt som pseudokode er gitt i Tabell 1 nedenfor. An overall overview of the method according to the present invention produced as pseudocode is given in Table 1 below.

Det skal bemerkes at LDAen (lenketetthetsanalysen) i følge den foreliggende oppfinnelsen kan betraktes som "en komponent" heller enn en løsning for dokumentbehandling. LDA skal anvendes som et steg nedstrøms for å erstatte BODY-elementet med en LDA identifisert artikkel og sette en "sideklassifiseringsattributt". Det skal bemerkes at LDA unngår bruk av bl.a. metatagger, å omdirigere trykk-siden for en artikkel og filtre på tekstverdier, regler basert på HTML-type, selekto-rer basert på elementklasser, filtre basert på hyppige ord for et nettsted eller undernettsted. Derfor er LDA i følge den foreliggende oppfinnelsen på en måte simplistisk. Videre er LDA lukket ettersom det ikke er noen mulighet for å plugge inn nye regler. Den eksponerer ikke terskler, for eksempel prosentandelen lenketekst for hvilken chunken ville bli klassifisert som en lenke eller innhold. It should be noted that the LDA (link density analysis) according to the present invention can be considered "a component" rather than a document processing solution. LDA shall be applied as a downstream step to replace the BODY element with an LDA identified article and set a "page classification attribute". It should be noted that LDA avoids the use of i.a. meta tags, redirecting the print page for an article and filters on text values, rules based on HTML type, selectors based on element classes, filters based on frequent words for a website or sub-site. Therefore, according to the present invention, LDA is in a way simplistic. Furthermore, the LDA is closed as there is no possibility to plug in new rules. It does not expose thresholds, such as the percentage of link text for which the chunk would be classified as a link or content.

Eksempel Example

På fig. 7. som viser en typisk webside med omkring 30% artikkelinnhold , ses det enkelt at mindre enn 30% av den viste siden består av tekstlig innhold i form av en artikkel, i dette tilfelle en historie med tittel "Let's Talk Jerky". Når lenkettheten og analysen i følge den foreliggende oppfinnelsen anvendes på dette dokumentet, kan resultatet presenteres som diagrammet vist i figur 8, som er en graf av klassifiserte sidechunker og statistikk brukt til klassifisering. En stor sammenhengende mengde chunker kommer ut med en lav lenketetthet, og er således vist som den store toppen eller kolonnen i diagrammet i fig. 8. Dette tolkes som artikkelinnhold og velges for fremvisning som vist i fig. 9, som selvsagt viser kun HTML eller artikkelinnholdet på denne siden. Hvordan lenketetthetsanalysen i følge den foreliggende oppfinnelsen virker, innses enkelt når fig. 9 sammenlignes med dokument-siden vist i fig. 7. In fig. 7. which shows a typical web page with about 30% article content, it is easily seen that less than 30% of the displayed page consists of textual content in the form of an article, in this case a story titled "Let's Talk Jerky". When the linkability and analysis according to the present invention is applied to this document, the result can be presented as the diagram shown in Figure 8, which is a graph of classified page chunks and statistics used for classification. A large contiguous amount of chunks emerges with a low link density, and is thus shown as the large peak or column in the diagram in fig. 8. This is interpreted as article content and selected for display as shown in fig. 9, which of course only displays the HTML or article content on this page. How the link density analysis according to the present invention works is easily realized when fig. 9 is compared with the document page shown in fig. 7.

Nå blir noen få representative og eksemplariske utførelsesformer beskrevet i noe detalj. • En komponent i en dokumentindekserende "pipeline", som identifiserer "tekst å indeksere" i en kildeside. A few representative and exemplary embodiments will now be described in some detail. • A component of a document indexing "pipeline", which identifies "text to index" in a source page.

• En "print side" fremvisningskomponent i en webapplikasjon. • A "print page" display component in a web application.

• En komponent i en applikasjon for "nettstedsanalyse" som identifiserer "artikkel" eller "nav"-sider i et nettsted, eller mønstre av sidekonstruksjoner over deler av nettstedet. • A component of a "site analytics" application that identifies "article" or "hub" pages within a website, or patterns of page construction across parts of the website.

Fordi fremgangsmåten i følge oppfinnelsen, som kunne vært benevnt "lenketthets-analyse", bruker sosiale normer med hensyn til dokumentlayout, og kun tar hensyn til HTMLs kodeskjema, er den per definisjon uavhengig av nettsted og språk. Som det vil være innlysende for fagfolk på området, er fremgangsmåten med lenketetthetsanalyse i den foreliggende oppfinnelsen generelt anvendbar på et-hvert masseprodusert HTML-innhold, og unngår de dyre, langsomme og feilutsatte fremgangsmåtene som er brukt hittil. Videre er lenketetthetsanalysen ikke nett-stedsspesifikk, og virker for enhver innholdsleverandør. Den er fordelaktig også uavhengig av språk, ettersom den kun er basert på strukturell analyse. Because the method according to the invention, which could have been named "linkness analysis", uses social norms with regard to document layout, and only takes into account HTML's coding scheme, it is by definition independent of website and language. As will be apparent to those skilled in the art, the method of link density analysis of the present invention is generally applicable to any mass-produced HTML content, and avoids the expensive, slow and error-prone methods used heretofore. Furthermore, the link density analysis is not site-specific, and works for any content provider. It is advantageous also regardless of language, as it is based only on structural analysis.

Claims

1. Procedure for identifying and extracting textual content in a document (web page) on the World Wide Web (WWW), where the document includes various types of content, including text, audio and video as well as navigators and associated links, and where the procedure includes steps for to map the document into components or sections called chunks, each chunk being identified by an HTML element such as <p> or <dib>, calculating the ratio of linked to unlinked content as a link density for the chunk, generating a graph of the sequence of the chunks' positions in the document against the calculated link density, and to extract a basic unlinked textual content of the document as the chunks that have the lowest overall link densities.

2. Procedure according to claim 1, characterized by extracting a contiguous amount of chunks with an overall low link density as a most likely textual content of the document, which contiguous amount of chunks is greater than a preset percentage threshold value in relation to the entire document.

3. Procedure according to claim 1, characterized by determining a threshold value for an acceptable maximum link density to optimize the proportion of textual content extracted from the document.