用於處理樹數據結構的方法

2023-09-22 02:26:40

專利名稱：：用於處理樹數據結構的方法用於處理樹數據結構的方法
技術領域：
：本發明涉及一種用於處理被組織到互連的元素的樹數據結構的方法。本發明一般應用於電信領域，尤其是經由網際網路的電信。然而，本發明的另一個特別有利的應用涉及連續地傳送元數據(流式傳輸)，尤其用於適合於分級的多媒體內容。MPEGSC29/WG11Ml1611(71stMPEGMeeting,HongKong,China,17/21-0l-2005)會議文獻定義對遵循由MPEG-21標準(ISO/IECTR2100-1:2004,Part1:Vision,TechnologiesandStrategy)定義的概念的數字項流式傳輸的方法，以及代表在MPEG-21環境中的基礎事務和分發單元。數字項是一個或多個語義上連結的多媒體內容(例如視頻、圖像、音頻)的摘要以及任何連結到那些內容的元數據，整個組成事務和終端用戶單元。以被廣泛地使用的樹數據結構語言即XML(可擴展標記語言)頻繁地寫連結到數字項的元數據。由於該數字項是用來通信的，其中可適用於經由網際網路類型的網絡，所以傳送包含在其中的元數據以及更普遍地傳送XML文件出現問題。具體地說，流式傳輸(連續地傳送)XML文件是有益的，所以目的地實體能夠使用其已經接收的片斷而沒必要等待接收整個文件。此外，有時XML文件的使用被連結到被連續地發送的諸如視頻流的其他數據的使用。然後有必要相互同步各種數據流，並且由此XML文件的片斷分配定時信息。以上提及的MPEG文獻提出一種用於分片數字項和分配定時信息給獲得的片斷的解決方案。其尤其適合於XML文件，雖然其並不局限於它們。該解決方案依靠Xpath表達式指示將被傳送的片斷，Xpath(XML路徑語言，version1.0，W3CRecommendation,16November1999)作為用於i口、別在XML文件中的節點或一組節點的表達式語言。此外，一個參數被用來定義用於那些片斷的傳送時間。然而，該現有技術的處理方法具有某些缺點首先，該方法使用表達式語言Xpath來選擇XML文件的片斷。對於Xpath的問題是整個XML文件必須被加載到存儲器以評價該表達式。對於小的XML文件，這不成問題。相反，對於大的文件，這能夠消耗相當大的存儲器資源並且能夠顯著地減j氐系統性能。第二，且出於相同的理由，該方法不能被用於動態(onthefly)生成的XML文件。第三，應用於片斷的定時信息無法定義對前趨的片斷的時間關係。與該
背景技術：
相反，將由本發明解決的技術問題將提出一種處理被組織成互連的元素的樹數據結構的方法，其使得特別是以XML類型的文件的形式選擇一組片斷成為可能，以及對它們靈活地分配定時信息。同樣，除了其無論將被流式傳輸的文件的大小如何都將要求有限的存儲器資源的事實外，此方法應當也適合於動態地生成的文件。根據本發明，對於所述的技術問題的解決方案存在於所述方法包括操作將處理單元定義為互連的元素的子集；和給每個處理單元分配處理時間，在此時間內與處理單元關聯的數據由編址所述數據至其的實體使用。本發明更特別地規定每個處理單元，其將基於稱為錨元素的給定元素被定義為按照給定附著模式連結到所述錨元素的一組元素。根據本發明，所述附著模式從以下模式中選出"簡單"、"祖先"、"後代"、"祖先和後代"、"祖先、後代、和前趨的兄弟姐妹"。以下定義這些不同的附著模式。本發明還規定將通過時間尋址模式和時間規範模式定義的所述處理時間。在本發明的第一實現中，所述時間尋址模式是絕對尋址模式並且處理單元的處理時間被絕對地按時間定義。所述處理時間規範模式則是按給定規範才各式的處理時間。在本發明的第二實現中，所述時間尋址模式是相對尋址模式並且處理單元的處理時間被相對前趨的處理單元而定義。所述處理時間規範模式由於是能夠被設想的時間間隔組成，且同樣地所述時間間隔被表示為在時標上的許多單位。如下詳細公開的，能夠靜態地或動態地實現本發明。更確切地，當靜態地實現時，依靠以樹的形式組織數據的文件實現的本發明的方法在此中值得注目分配給所述元素的模式在所述文件中被指定。此外，當動態地實現時，依靠以樹的形式組織數據的文件實現的本發明的方法在此中值得注目所述文件4皮與在其中指定分配給顧及所迷文件的元素的模式的模板文件相關聯。尤其，存在對包含一組模板的所述模板文件的規定，每個模板由模板模式和由將為該元素或滿足所述模板模式的元素指定的一組屬性定義。最後，本發明也涉及用於實現本發明的方法的伺服器，涉及包括用於當程序在計算機中執行時執行本發明的方法的程序代碼指令的電腦程式，並且涉及代表以樹(其依靠屬性指定處理單元和關聯的處理時間)的形式組織數據的文件的信號。作為非限制性示例，參考附圖的以下描述，清楚地解釋本發明由什麼組成以及其如何能夠變為現實。圖1顯示互連元素的樹結構。圖2a、2b和2c顯示來自圖l樹結構的三個處理單元。圖3顯示與圖1樹結構關聯的XML文件。圖4a、4b和4c顯示分別與來自圖2a、2b和2c的各處理單元關聯的XML文件。圖5顯示依照本發明的處理方法的與來自圖2a、2b和2c的各處理單元關聯的XML文件。圖6顯示圖2c的處理單元的變體。圖7顯示圖5中與圖6的變體關聯的XML文件的變體。圖8顯示來自圖5的包括用於該處理單元的處理時間屬性的XML文件。圖9顯示與圖3的XML文件關聯的模板文件。圖10顯示由本發明的方法使用的屬性和模3反的語法。圖11是顯示根據本發明的方法，(a)在靜態模式和(b)在動態模式中來自圖3的XML文件的元素的處理流的圖。圖1顯示被組織成互連元素的樹數據結構。元素對應於樹的節點並且一般由字母el標識。樹的第一個元素稱為根。圖2a、2b和2c顯示此結構的三個處理單元UTl、UT2、UT3，其作為同樣能夠由目的地實體使用的樹的子集、或片斷。片斷是任何相連的元素組。處理單元UT1包括元素e10和ell，處理單元UT2包括元素EIO、e12,e121和e1211，以及處理單元UT3包括元素e10、e12、e122、e1221和e1222。圖3XML文件與圖l樹結構關聯。當然，本發明不單單局限於XML文件並且能夠應用於任何樹數據結構。假設目的地應用能夠連續地使用該文件。關於這點，處理單元是文件的片斷，其能夠被獨立於文件的其餘部分而使用。圖4a、4b和4c顯示從圖3的原始文件中提取的XML文件，其可以分別與處理單元UT1、UT2和UT3相關^:,並且與該原始文件獨立地存〗諸在月良務器的存儲器中。然而，該解決方案將引入由數據的冗餘導致的不一致的風險，以及不必要的消耗存儲器空間和帶寬。為了避免這些缺點，本發明提出以下參照圖5到IO描述的處理方法。一般而言，元分配處理時間，據的目的地的實體使用。基於稱為錨元素的給定元素將處理單元定義為按照給定附著模式連結到所述錨元素的一組元素。在圖2a、2b和2c中，處理單元UT1、Un和UT3的錨元素分別是由樹中的白圓圈表示的ell、e1211和el22。能夠設想各種附著模式，即，"簡單"、"祖先"、"後代"、"祖先和後代"、以及"祖先、後代和前趨的兄弟姐妹"附著模式。在"筒單"附著模式中，該處理單元僅包含錨元素本身。在"祖先，，附著模式中，該處理單元包含錨元素和它的全部祖先。在"後代，，附著才莫式中，該處理單元包含錨元素和它的全部後代。在"祖先和後代"附著模式中，該處理單元包含錨元素、它的全部後代和它的全部^L先。在"祖先、後代和前趨的兄弟姐妹"附著模式中，該處理單元包含錨元素、它的後代、它的祖先、它的祖先之前的元素以及它們的後代。在圖2a、2b和2c中，通過對其各自的錨元素應用"祖先和後代"附著模式來定義處理單元UT1、UT2和UT3。使用錨元素和附著模式概念來定義應用到樹結構的、將^f皮流式傳輸到目的地實體的元素的性質。錨元素概念對應於某一元素是或不是錨元素的性質。相似的，附著模式概念對應於某一元素根據給定附著一莫式附著到該錨元素的性質。才艮據"祖先元素，，性質，祖先元素定義一個並且僅僅一個處理單元。相對地，其可能屬於其他處理單元。處理單元由一個JU又僅一個錨元素相互地識別。相反，它能夠包含其它錨元素。當本發明的處理方法通過例如XML文件實現時，元素的性質通過XML屬性定義或者從其父母元素中繼承。圖5顯示來自圖2a、2b和2c的各處理單元如何能夠在圖3所示的原始XML文件中被靜態地選擇。在分配給元素ell、el211和el22的"anchorElement"屬性中反映"錨元素"性質。該錨元素屬性的值是布爾值如果且僅僅如果元素包含具有值"真"的"錨元素"屬性，則其是錨元素。為XML文件的元素定義的次序關係存在，其對應於下列導向路徑隨著文件從左至右和從上至下掃描，元素的次序是開放標籤發生的次序。例如，在圖3的文件中，元素被如下排序(e10，ell,e12，e121，e1211,e122,e1221，e1222,el3}。處理單元的次序是定義它們的錨元素的次序。尤其對於定義相對於前趨的處理單元的處理單元的處理時間的相對時間尋址，該次序在下面使用。注意在元素無法從父母元素中繼承性質的意義下，"錨元素"性質無法被繼承。在被用來基於該錨元素選擇處理單元的"puMode"屬性中反映連結到附著模式的第二性質。此性質直接由"puMode"屬性定義或者從父母元素中繼承。其值是下面中的一個*"自己"用於"簡單"附著模式；*"祖先，，用於"祖先"附著衝莫式；*"後代，，用於"後代"附著才莫式；"祖先後代"用於"祖先和後代"附著模式；"祖先後代前趨的兄弟姐妹，，用於"祖先、後代和前趨的兄弟姐妹"附著模式。在圖5所示的文件中，"puMode，，屬性被用於根元素e10來定義具有例如值"祖先後代"的性質puMode。這裡此性質被該文件的全部元素繼承。由此錨元素ell,el211和el22繼承此性質。由此，每個將處理單元定義為如上解釋的性質的函數。依此方式定義的處理器單元UTi、un和un對應於在圖4a、4b和4c中表示的和在圖2a、2b和2c中圖示的三個文件。在此例中，"puMode"性質一旦被"puMode"屬性定義用於根元素，然後就被其它元素繼承。同樣可能獨立地為其它元素定義此性質。如果圖2c的處理器單元UT3由圖6的處理器單元UT'3取代，對此錨元素仍然是元素e122但是對於該元素，"puMode，，性質通過"後代"附著模式定義，則"puMode，，屬性的"後代"值必須在錨元素el22中指定。由本發明提出的用於按照屬性和繼承定義性質的機制並且由此定義具有良好顆粒度(即，如果有必要，對於每個元素獨立)的性質並且其有效地如果文件的子樹的元素享有相同的性質，則沒有必要將屬性加至每個元素來定義該性質。將屬性加到子樹的根元素就足夠了並且然後依此方式定義的性質被其全部後代繼承。第一性質timeMode定義時間尋址才莫式。其通過"timeMode"屬性定義或者從父母元素繼承。"timeMode，，屬性的值如下*"未定義"時間尋址^t式沒有定義；*"相對，，時間尋址模式是相對的，即，處理單元的處理時間相對於前趨的單元被定義；*"絕對，，時間尋址模式是絕對的，即，絕對地定義處理單元的處理時間；第二性質timeScale定義用於相對時間尋址的時標。其通過"timeScale"屬性定義或者從父母元素中繼承。其值是定義時標的整數，即，每秒單位數目。第三性質timeinterval定義介於用於相對時間尋址的兩個連續處理單元之間的時間間隔。其通過"timelnterval"屬性定義或者從父母元素中繼承。其值是定義相對於前趨處理單元的時間單位的數目的整數，該時間單位由上面定義的timeScale性質定義。第四性質absTimeScheme定義用於絕對時間尋址的時間格式。其通過"absTimeScheme，，屬性定義或者從父母元素中繼承。其值是定義時間尋址格式的字符流。例如，流"mp7t"指示由MPEG-7MDS(MediaTimePointType)定義的時間尋址格式。最後，第五性質absTime定義用於絕對時間尋址的處理時間。其不可繼承，且通過"absTime，，屬性定義。其值是根據由absTimeScheme性質定義的時間尋址才各式定義的時間的字符流。對於MPEG-7地址格式，此值的一個例子是"丁17:30:45:2F10"。例如，在圖8所示的文件中，應用於根節點e10的"timeMode"、"timeScale，，和"timelnterval"屬性指示關於該元素的時間尋址是相對的，時標是22050單位每秒，並且在兩個處理單元之間的間隔是1024單位。這裡這些性質糹皮文件的元素並且尤其是錨元素繼承。處理單元從它們各自的錨元素中繼承這些性質。由此處理單元UTl將在時間tl-O處被呈現給目的地應用，處理單元UT2在時間t2=l024/22050秒處，以及處理單元UT3在時間t3-2048/22050秒處。上面已經顯示如何能夠依靠靜態添加到原始文件(如圖8說明的文件)的屬性來指定定義處理單元和其關聯的處理時間的性質。下面解釋如何能夠通過應用一組才莫板來動態地添加屬性。在此動態實現中，如同圖3所示的原始XML文件與模板文件關聯，其中通過模板模式定義每個模板。此模式定義該模板將被應用到的XML元素和然後將被添加到這些元素的一組屬性。在圖io中定義全部屬性和模板的語法。圖9給出動態模板文件的例子。此例的結果與使用來自圖8的靜態指令一致。遵照STX(StreamingTransformationsforXML(STX)，Version1.0，WorkingDraft1July2004)中定義的表達式語言STXPath的語法，寫該模板模式。STX是用於變換動態的XML文件，即，沒必要首先將全部文件加載到存儲器。這允許變換大的XML文件和動態生成的並且因此使得其整體是不可用的文件。由此STXPath特別適合於本發明的上下文。STXPath語法與XPath接近。相反，它的語義有別。如在STXPath中，在XPath中，相對於上下文元素分解表達式。為評價此表達式，XPath必須考慮存在於整個文件的上下文。相反，STXPath僅考慮該上下文元素和其祖先的棧。由此在STXPath中解析必需的上下文是有限的且特別適合本發明的上下文。STXPath尤其被用來表達關於上下文的元素的名稱、其序數、及其可能的屬性的名稱和值的約束。例如，XPath表達式"/ell/el2"選擇其父母元素名為eil並且是該文件的根的全部名為d2的元素。在STXPath中相同的表達式選擇最多一個元素，即，在上下文元素的祖先的棧中的元素，其父母元素是名為el2且其父母名為ell。給定實現能夠使用STXPath的子集來提供既靈活又快速的過濾過程。下面參考圖11解釋依照本發明的方法的，在(a)靜態模式和(b)動態模式中圖3的XML文件的元素處理。通過稱為語法分析器(解析器)的軟體模塊讀原始的XML文件。幾類解析器被廣泛使用。這些模塊允許應用經由給定應用程式接口(API)存取包含在XML文件中的信息。通過由網站聯盟(XMLInformationSet(SecondEdition),W3CRecommendation4February2004)標準化的稱為信息組(Infoset)的摘要模塊模擬所有包含在XML文件中的信息。本發明能夠被用於幾種類型的解析器，諸如DOM(文件對象模型)(DocumentObjectSystemLevel2CoreSpecification,Version1.0,W3CRecommendation13November2004)或SAX(用於XML的簡單API)。在此描述的本發明使用SAX，一種就存儲器消耗而言高效的實現。SAX類型的解析器讀XML文件並且輸出一序列描迷該內容的事件。例如，讀圖3中表示的一般文件基本引起以下事件序列Complextableseetheoriginaldocumentpage12本發明利用定義處理單元的信息充實XML文件的信息組。在靜態模式(a)中，如圖8所示，屬性被加入原始文件中。SAX解析器因而產生包含充實了信息的SAX事件序列。在動態模式(b)中，通過分析原始文件生成的事件由一組(bank)模板處理以動態添加屬性。稱為流指令處理器的模塊接收通過讀原始文件而由解析器輸出的SAX事件作為輸入，應用在稱為動態流指令的文件中規定的模板，並且輸出包含充實了信息的SAX事件序列。由此編碼器接收充實了流指令(正如設想該指令已經被靜態地添加到原始XML文件)的信息組。由此該處理的其餘部分與靜態指令的情形一致。編碼器然後使用定義處理單元的信息來編碼它們。編碼器的輸出存在於一序列存取單元UA中，其是經編碼用於傳輸的的數據實體，從而解碼該連續的存取單元重建由流指令定義的處理單元。能夠使用幾種編碼方法，諸如MPEG-7系統(ISO/IEC15938-1:2002,Part1:Systems)、TeM(文字編碼)或BiM(二進位編碼)。對於每種編碼方法可能有幾種編碼策略。然後存取單元能夠經由網絡(例如網際網路)被發送或連接在存儲器中以便稍後發送。圖ll顯示這兩種情況。在每種情況下，當其被解碼之後可被應用時，每個存取單元與指定時間的處理時間關聯，在該時間處理單元必須可用於目的地實體以便被使用。圖11的右側顯示由目的地實體使用存取單元。權利要求1.一種處理被組織成互連的元素的樹數據結構的方法，其特徵在於所述方法包括操作將處理單元定義為互連元素的子集；以及給每個處理單元分配處理時間，在該處理時間期間關聯的處理單元的數據將由尋址所述數據的實體使用。2.如權利要求l所述的方法，其特徵在於基於稱為錨元素的給定元素將每個處理單元定義為按照給定附著模式連結到所述錨元素的一組元素。3.如權利要求2所述的方法，其特徵在於所述附著模式從以下模式中選出"簡單"、"祖先"、"後代"、"祖先和後代"、以及"祖先、後代和前趨的兄弟姐妹"。4.如權利要求1到3中任何一項所述的方法，其特徵在於通過時間尋址模式和時間規範模式定義所述處理時間。5.如權利要求4所述的方法，其特徵在於所述時間尋址模式是絕對尋址模式並且該處理單元的處理時間被絕對地按時間定義。6.如權利要求5所述的方法，其特徵在於所述處理時間規範模式則是按給定規範格式的處理時間。7.如權利要求4所述的方法，其特徵在於所述時間尋址模式是相對尋址8.如權利要求7所述的方法，其特徵在於該處理時間規範模式是時間間隔。9.如權利要求8所述的方法，其特徵在於所述時間間隔被表示為在時標上的多個單位。10.如權利要求2到9中任何一項所述的方法，其依靠以樹的形式組織數據的文件來實現，其特徵在於在所述文件中指定已分配給所述元素的模式。11.如權利要求10所述的方法，其特徵在於在所述文件中處理單元的每個錨元素淨皮分配指定對應元素的錨元素字符的"anchorEleraent"屬性和指定與所述錨元素關聯的附著模式的"puMode"屬性。12.如權利要求11所述的方法，其特徵在於為給定元素分配的"puMode"13.如權利要求12所述的方法，其特徵在於為給定元素分配的"puMode"屬性被在該文件中的所述給定元素的全部後代元素繼承，直到一個分配了不同於所述屬性的"puMode"屬性的元素。14.如權利要求11到13中任何一項所述的方法，其特徵在於通過分配給所述單元的錨元素的"puMode，，屬性確定處理單元的附著才莫式。15.如權利要求11或12所述的方法，其特徵在於給每個處理單元的元素分配時間尋址"timeMode，'屬性和時間失見範屬性。16.如權利要求15所述的方法，其特徵在於在絕對時間尋址模式中所述時間規範屬性包括在時間規範格式中的"absTinieScheme"屬性和用於指定在所述格式中的處理時間的"absTime".屬性。17.如權利要求15所述的方法，其特徵在於在相對時間尋址模式中所述時間規範屬性包括指示"timeScale"的時標屬性和指示"timelnterval"的時間間隔屬性。18.如權利要求15到17所述的方法，其特徵在於分配給給定元素的"timeMode"、"absTimeScheme，，、"timeScale'，、和"timelnterval'，屬性被在該文件中的所述給定元素的全部後代元素繼承。19.如權利要求15到18所述的方法，其特徵在於分配給給定元素的"UmeMode，'、"absTimeScheme'，、"timeScale，'、和"timelnterval，，屬性被在該文件中的所述^^定元素的全部後代元素繼K,直到一個分配了不同於所述屬性的"UmeMode"、"absTimeScheme，，、"timeScale"、或"timelnterval"屬性的元素。20.如權利要求15到19中任何一項所述的方法，其特徵在於處理單元的時間尋址模式、時間規範格式、時標和時間間隔由分配給所述單元的錨元素的"timeMode，，、"absTimeSchen]e"、"timeScale，'、和"timelnterval"屬性確定。21.如權利要求2到9中任何一項所述的方法，其依靠以樹的形式組織數據的文件來實現，其特徵在於所述文件與模^^反文件關聯，在該才莫板文件中，指定分配給所述文件的有關的元素的模式。22.如權利要求21所述的方法，其特徵在於所述模板文件包括一組模板，每個模板由模板模式和由將為滿足所述模板模式的一個或多個元素指定的一組屬性定義。23.如權利要求22所述的方法，其特徵在於如果存在，則應用於給定元素的所述模板模式指定關於所述給定元素的祖先序列、所述給定元素本身、和其屬性的一個或多個條件。24.如權利要求23所述的方法，其特徵在於所述條件被適配於約束所述元素的名稱和序數以及所述屬性的名稱和值。25.—種用於實現根據權利要求1到24中任何一種方法的伺服器。26.—種包括用於當所述程序在計算機中執行時執行根據權利要求1到24中任何一種方法的程序代碼指令的電腦程式。27.—種代表以樹的形式組織數據的文件的信號，其依靠"anchorElement，'、"p函de"、"timeMode，，、"absTimeScheme"、"absTime""timeScale，，或"timelnterval"屬性指定處理單元和關聯的處理時間。全文摘要本發明涉及一種用於處理被組織成互連的元素的樹數據結構的方法。根據本發明，該方法包括步驟作為互連的元素的子集的處理單元的定義，向每個處理單元分配處理數據，在其中經分配的處理單元的數據將被由用於所述數據的接收單元使用。以上是漸進傳輸元數據的有關應用，尤其是適合於分級的多媒體內容。文檔編號G06F17/30GK101198954SQ200680020972公開日2008年6月11日申請日期2006年4月7日優先權日2005年4月12日發明者亞歷山大·科塔馬納克,西爾萬·德維勒斯申請人:法國電信公司