Simplex tree
টপোলজিক্যাল ডেটা বিশ্লেষণে, একটি সিম্প্লেক্স ট্রি হল এক ধরনের ট্রাই যা দক্ষতার সাথে যে কোনও সাধারণ সরল জটিলতার প্রতিনিধিত্ব করতে ব্যবহৃত হয়। এর নোডগুলির মাধ্যমে, এই তথ্য কাঠামোটি স্পষ্টভাবে সমস্ত সরলীকরণের প্রতিনিধিত্ব করে। এর নমনীয় কাঠামো স্থায়ী সমসংস্থান গণনার জন্য দরকারী অনেক মৌলিক ক্রিয়াকলাপ বাস্তবায়নের অনুমতি দেয়। এই তথ্য কাঠামোটি 2014 সালে জিন-ড্যানিয়েল বোইসোনাট এবং ক্লেমেন্ট মারিয়া 'দ্য সিম্প্লেক্স ট্রিঃ অ্যান এফিশিয়েন্ট ডেটা স্ট্রাকচার ফর জেনারেল সিম্প্লিসিয়াল কমপ্লেক্সস' প্রবন্ধে উদ্ভাবন করেছিলেন। এই তথ্য কাঠামো বিরল সরল জটিলতার উপর দক্ষ ক্রিয়াকলাপ সরবরাহ করে। ঘন বা সর্বাধিক সরলীকরণের জন্য, স্কেলেটন-ব্লকার উপস্থাপনা বা টপলেক্স মানচিত্র উপস্থাপনা ব্যবহার করা হয়। সংজ্ঞা টপোলজিক্যাল ডেটা বিশ্লেষণে অনেক গবেষক সিম্প্লেক্স গাছকে সরল জটিলতার জন্য সবচেয়ে সংক্ষিপ্ত সিম্প্লেক্স-ভিত্তিক ডেটা স্ট্রাকচার এবং একটি ডেটা স্ট্রাকচার হিসাবে বিবেচনা করেন যা তাদের গাণিতিক বৈশিষ্ট্যগুলির সমন্বিত ব্যবহারের কারণে সরল জটিলতার স্বজ্ঞাত বোঝার অনুমতি দেয়। অনুসন্ধানমূলক সংজ্ঞা বিবেচনা করুন যে কোনও সরল জটিল হল বিন্দু (0 মাত্রা), রেখা বিভাগ (1 মাত্রা), ত্রিভুজ (2 মাত্রা) এবং তাদের এন-মাত্রিক প্রতিরূপগুলির সমন্বয়ে গঠিত একটি সেট, যাকে একটি টপোলজিকাল স্থানের মধ্যে এন-সিম্প্লেক্স বলা হয়। সিম্প্লেক্সের গাণিতিক বৈশিষ্ট্য অনুসারে, যে কোনও এন-সিম্প্লেক্স একাধিক-সিম্প্লেক্স নিয়ে গঠিত। সুতরাং, রেখাগুলি বিন্দু, রেখার ত্রিভুজ, ত্রিভুজের টেট্রাহেড্রন নিয়ে গঠিত। লক্ষ্য করুন প্রতিটি উচ্চতর স্তর এন-সিম্প্লেক্সের শীর্ষে 1টি শীর্ষ যোগ করে। ডেটা স্ট্রাকচারটি সিম্প্লেক্স-ভিত্তিক, তাই, এটি সিম্প্লেক্সকে সংজ্ঞায়িত পয়েন্ট দ্বারা সমস্ত সিম্প্লেক্সকে অনন্যভাবে উপস্থাপন করা উচিত। এটি অর্জনের একটি সহজ উপায় হল প্রতিটি সিম্প্লেক্সকে তার পয়েন্ট দ্বারা সাজানো ক্রমে সংজ্ঞায়িত করা। ধরা যাক মাত্রা k-এর একটি সরল জটিল, এর ভার্টেক্স সেট, যেখানে শীর্ষগুলি 1 থেকে চিহ্নিত করা হয় এবং সেই অনুযায়ী সাজানো হয়। এখন, একটি অভিধানের আকার তৈরি করুন যাতে ক্রমানুসারে সমস্ত ভার্টেক্স লেবেল রয়েছে। এটি 0-মাত্রিক সিম্প্লেক্সের প্রতিনিধিত্ব করে। তারপর, প্রাথমিক অভিধানে প্রতিটি এন্ট্রির প্রাথমিক অভিধানের পথের জন্য, একটি শিশু অভিধান হিসাবে সমস্ত শীর্ষগুলি বর্তমান শীর্ষগুলির সেটের সাথে সম্পূর্ণরূপে সংযুক্ত করুন, যার সবকটিরই একটি লেবেল রয়েছে। কে স্তরে এই ধাপটি উপস্থাপন করুন। স্পষ্টতই, প্রথম অভিধানটিকে গভীরতা 0 হিসাবে বিবেচনা করে, এই তথ্য কাঠামোর যে কোনও অভিধানের গভীরতায় যে কোনও এন্ট্রি অনন্যভাবে একটি-সরলতা উপস্থাপন করে। সম্পূর্ণতার জন্য, প্রাথমিক অভিধানের বিন্দুটিকে খালি সিম্প্লেক্সের উপস্থাপনা হিসাবে বিবেচনা করা হয়। ক্রিয়াকলাপের কার্যকারিতার জন্য, একই স্তরে পুনরাবৃত্তি করা লেবেলগুলি একসাথে সংযুক্ত করা হয়, একটি লুপযুক্ত লিঙ্কযুক্ত তালিকা তৈরি করে। পরিশেষে, শিশু অভিধানগুলিতে দ্রুত পূর্বপুরুষদের প্রবেশাধিকারের জন্য তাদের মূল অভিধানের নির্দেশকও রয়েছে। গঠনমূলক সংজ্ঞা ধরা যাক k মাত্রার একটি সরল জটিল। আমরা সরল জটিলটিকে পারস্পরিক একচেটিয়া সরলরেখায় বিভক্ত করে শুরু করি। সরল কমপ্লেক্সটি খালি না হওয়া পর্যন্ত সরল কমপ্লেক্স থেকে সর্বোচ্চ ক্রমের সিম্প্লেক্সগুলি পুনরাবৃত্তভাবে অপসারণ করে এটি একটি লোভী উপায়ে অর্জন করা যেতে পারে। তারপরে আমাদের প্রতিটি শীর্ষকে 1 থেকে লেবেল করতে হবে এবং প্রতিটি সিম্প্লেক্সকে তার সংশ্লিষ্ট "শব্দ" এর সাথে সংযুক্ত করতে হবে, যা লেবেল দ্বারা তার শীর্ষগুলির ক্রমযুক্ত তালিকা। লেবেলগুলি অর্ডার করা নিশ্চিত করে যে সিম্প্লেক্স ট্রি-তে কোনও পুনরাবৃত্তি হবে না, কারণ সিম্প্লেক্স বর্ণনা করার একমাত্র উপায় রয়েছে। আমরা একটি নাল রুট দিয়ে শুরু করি, যা নাল সিমপ্লেক্সের প্রতিনিধিত্ব করে। তারপর, আমরা সমস্ত সিম্প্লেক্সের মাধ্যমে এবং প্রতিটি সিম্প্লেক্স শব্দের প্রতিটি লেবেলের মাধ্যমে পুনরাবৃত্তি করি। যদি লেবেলটি বর্তমান মূলে একটি শিশু হিসাবে উপলব্ধ থাকে, তবে সেই শিশুকে সন্নিবেশ প্রক্রিয়ার অস্থায়ী মূল করুন, অন্যথায়, শিশুর জন্য একটি নতুন নোড তৈরি করুন, এটিকে নতুন অস্থায়ী মূল করুন এবং বাকি শব্দের সাথে চালিয়ে যান। এই প্রক্রিয়া চলাকালীন, কে অভিধানগুলি সমস্ত লেবেলের সাথে রক্ষণাবেক্ষণ করা হয় এবং সংশ্লিষ্ট লেবেলের জন্য নোডের ঠিকানা সন্নিবেশ করা হয়। যদি অভিধানের সেই জায়গায় ইতিমধ্যেই কোনও ঠিকানা থাকে, তাহলে পুরনো নোড থেকে নতুন নোডে একটি পয়েন্টার তৈরি করা হয়। একবার প্রক্রিয়াটি শেষ হয়ে গেলে প্রতিটি নোডের সমস্ত শিশুদের একটি অভিধানে প্রবেশ করানো হয় এবং সমস্ত পয়েন্টারগুলি লুপ করা লিঙ্কযুক্ত তালিকা তৈরি করার জন্য লুপ করা হয়। হ্যাশ টেবিলের মতো বিস্তৃত অভিধান এখানে প্রয়োগ করা যেতে পারে, তবে কিছু ক্রিয়াকলাপ এন্ট্রিগুলির একটি ক্রমযুক্ত ট্র্যাভারসালের সম্ভাবনা অনুমান করে, যার ফলে বেশিরভাগ বাস্তবায়নে লাল-কালো গাছ ব্যবহার করা হয় অভিধান। সরল জটিল উপস্থাপনার জন্য সিম্প্লেক্স গাছগুলি সবচেয়ে স্থান দক্ষ তথ্য কাঠামো না হলেও, বিরল তথ্যের উপর তাদের ক্রিয়াকলাপকে অত্যাধুনিক হিসাবে বিবেচনা করা হয়। এখানে, আমরা এই উপস্থাপনার মাধ্যমে সম্ভাব্য বিভিন্ন দরকারী ক্রিয়াকলাপের সীমা প্রদান করি। এই ক্রিয়াকলাপগুলির অনেকগুলি বাস্তবায়ন উপলব্ধ। আমরা প্রথমে স্বরলিপিটি প্রবর্তন করি। বিবেচনা করুন একটি প্রদত্ত সিম্প্লেক্স, একটি প্রদত্ত নোড যা এর শেষ শীর্ষের সাথে সম্পর্কিত, সেই নোডের লেবেল সহযোগী, সেই নোডের গভীরতা, সরল জটিলতার মাত্রা, একটি অভিধানে অ্যাক্সেস করার জন্য ক্রিয়াকলাপের সর্বাধিক সংখ্যা (যদি অভিধানটি একটি লাল-কালো গাছ হয়, তবে জটিলতা)। কোফেসগুলির সংখ্যা বিবেচনা করুন, এবং এর চেয়ে বেশি গভীরতায় লেবেলের সাথে শেষ হওয়া সিম্প্লেক্স গাছের নোডের সংখ্যা। লক্ষ্য করুন। শব্দ অনুসন্ধান, সন্নিবেশ এবং অপসারণ করা হয়। একটি সম্পূর্ণ সিম্প্লেক্স ঢোকান এবং সরিয়ে ফেলুন। স্থায়ী সমসংস্থান গণনা করা, বা আরও জড়িত উপায়ে, বেটি সংখ্যা গণনা করা, একটি সিম্প্লেক্স ট্রি ব্যবহার করে সবচেয়ে দক্ষতার সাথে একটি উন্মুক্ত সমস্যা রয়ে গেছে, তবে, বিরল সরল জটিলতার উপর এই কাজের জন্য বর্তমান অ্যালগরিদমগুলি অত্যাধুনিক কর্মক্ষমতা অর্জন করে। সিম্প্লেক্স গাছের কাঠামো সংকুচিতযোগ্য সিম্প্লেক্সগুলির প্রাথমিক পতনের অনুমতি দেয়, তবে সাধারণ ক্ষেত্রে এই ক্রিয়াকলাপের সীমা অজানা। প্রাথমিক পতনের একটি উপ-কেস হল প্রান্ত-সংকোচন। প্রান্ত সংকোচন অর্জন করা যেতে পারে। প্রদত্ত সিমপ্লেক্সের অবস্থান নির্ণয় করা যেতে পারে। প্রদত্ত সিমপ্লেক্সের কোফ্যাসেটগুলি সনাক্ত করা সম্ভব। নির্মাণের ক্ষেত্রে, গঠনমূলক সংজ্ঞায় যেমন দেখা যায়, নির্মাণ সরল জটিলতায় সিম্প্লেক্সের সংখ্যা এবং জটিলতার সাথে আনুপাতিক। এটি বিশেষভাবে ব্যয়বহুল হতে পারে যদি সরল পরিসরটি ঘন হয়। যাইহোক, ফ্ল্যাগ কমপ্লেক্স, রিপস কমপ্লেক্স এবং উইটনেস কমপ্লেক্স সহ নির্দিষ্ট সরল কমপ্লেক্সগুলির জন্য কিছু অপ্টিমাইজেশন। অ্যাপ্লিকেশন সিম্প্লেক্স ট্রি বিরল সরল জটিলতায় কার্যকর। এই উদ্দেশ্যে, উচ্চ-মাত্রিক বাস্তব তথ্যের (প্রায়শই বিরল) উপর দৃষ্টি নিবদ্ধ করে অনেক স্থায়ী সমসংস্থান অ্যালগরিদম এই অ্যালগরিদমগুলির মধ্যে সিম্প্লেক্স ট্রি ব্যবহার করে। যদিও সিম্প্লেক্স গাছগুলি আপতন ম্যাট্রিক্সের মতো দক্ষ নয়, তাদের সিম্প্লেক্স-ভিত্তিক কাঠামো তাদের স্থায়ী সমসংস্থান অ্যালগরিদমের মধ্যে সহজ জটিল সংরক্ষণের জন্য কার্যকর দক্ষ হতে দেয়। তথ্যসূত্র গাছ (তথ্য কাঠামো) সহজ সেট